Valid BST Preorder Verification

You are given a sequence of unique integers. The sequence represents a proposed preorder traversal of a binary search tree (BST). Your task is to verify if the sequence can indeed be the preorder traversal of a BST.

A valid BST is defined as follows: for any node with value v, all values in its left subtree must be less than v and all values in its right subtree must be greater than v. Moreover, when the BST is traversed in preorder (visiting the root first, then left subtree, then right subtree), the resulting traversal must match exactly with the given sequence.

If the sequence corresponds to the preorder traversal of a valid BST, output YES, otherwise output NO.

Note: An empty sequence or a sequence with a single element is always considered valid.

inputFormat

The first line of input contains an integer T (T ≥ 1) representing the number of test cases. Each test case is described in two lines:

• The first line contains an integer n (n ≥ 0) denoting the number of nodes.
• The second line contains n space-separated unique integers.

If n is 0, the second line will be empty.

outputFormat

For each test case, output a single line with the result YES if the sequence can form a valid BST (as its preorder traversal), otherwise output NO.

## sample

3
5
1 3 2 4 5
4
2 1 3 4
6
7 4 6 3 8 10

YES
YES
NO

</p>