You are given an array h_1, h_2, \ldots, h_n of integers. Split it into two subsequences, that is, assign every element to exactly one of two subsequences (either of them may be empty), so that:
the first subsequence is non-decreasing: if it consists of the elements with indices i_1 < i_2 < \ldots < i_k, then h_{i_1} \le h_{i_2} \le \ldots \le h_{i_k};
the second subsequence is non-increasing: if it consists of the elements with indices j_1 < j_2 < \ldots < j_l, then h_{j_1} \ge h_{j_2} \ge \ldots \ge h_{j_l}.
Determine whether such a split exists.
The first line contains a single integer (1 \le t \le 10^4) — the number of test cases.
Each test case consists of two lines. The first line contains an integer (1 \le n \le 10^6) — the length of the array. The second line contains integers h_1, h_2, \ldots, h_n (0 \le h_i \le 10^9).
The sum of over all test cases does not exceed 10^6.
For each test case, print a line YES if a suitable split exists, and NO otherwise.
The words YES and NO may be printed in any letter case.
Example 1
In the first test case h = [3, 5, 5, 2, 6, 1], and a suitable split exists, so the answer is YES.
For example, the non-decreasing subsequence may be , and the non-increasing subsequence 5, 5, 2, 1.
Another suitable split: the non-decreasing subsequence is 3, 5, 5, 6, and the non-increasing subsequence is .
The figure shows the first of these splits: the non-decreasing subsequence is dark (solid line), and the non-increasing one is light (dashed line).
In the second test case h = [2, 1, 4, 3]. Suppose that the element belongs to the non-increasing subsequence.
Then the earlier and smaller elements and cannot belong to it, so both belong to the non-decreasing subsequence, but that subsequence cannot contain followed by .
So the element belongs to the non-decreasing subsequence, and then the later and smaller element belongs to the non-increasing one.
Now the elements and are earlier and smaller than , so they cannot belong to the non-increasing subsequence, and again both would belong to the non-decreasing one, which is impossible.
Hence the answer is NO.
In the third test case all elements can belong to one subsequence, and the other one stays empty.
In the fifth test case the non-increasing subsequence is , and the non-decreasing subsequence is .