Yet Another Array Problem!

On the occasion of Independence Day, Punjab Engineering College decides to conduct a Flag Hoisting Ceremony and decides to give Flag Hoisting opportunity to one of the students. So, they decide to give students an interesting array problem and the student which comes up with the best solution fastest gets the golden opportunity.

Formally, the problem is described below.

You are given an array A with N integers. You can remove an element either from the front or end of the array A and append it to another array B (initially B is empty). You have to simulate this process till there is atleast one element left in A . The task seems pretty easy but isn't. You have to find is there any way to perform the above steps in any order such that the we get B sorted in non-decreasing fashion.

Akshit doesn't want to miss this golden opportunity but since he is a noob in programming, he asks your help to solve this problem for him. Can you solve it for him?

Input Format:

• The first line of the input contains a single integer T denoting the number of test cases. The description of T test cases follows.
• The first line of each test case contains a single integer N, the number of elements present in the array A.
• The second line contains N space-separated integers A1,A2,...,AN.

Output Format:

For each test case, print a single line containing a string "YES" if there is a way to perform the above steps in any order such that the we get B sorted in non-decreasing fashion else print "NO".

Constraints:

1T10⁵

1N10⁶

1Ai10⁴

Sum of N over all test cases doesn't exceed 310⁶

SAMPLE INPUT

3

3

1 2 5

5

1 2 2 3 1

7

3 5 7 2 1 5 3

SAMPLE OUTPUT

YES

YES

NO

Explanation

Testcase 2:

Initial Configuration of A and B.

A=[1,2,2,3,1]B=[]

Steps:

Remove A[0] and append it to B.A=[2,2,3,1]B=[1]

Remove A[3] and append it to B.A=[2,2,3]B=[1,1]

Remove A[0] and append it to B.A=[2,3]B=[1,1,2]

Remove A[0] and append it to B.A=[3]B=[1,1,2,2]

Remove A[0] and append it to B.A=[2,3]B=[1,1,2,2,3]

We get B as desired.

You are expected to think about testcases 1 and 3 on your own.