Time Limit: 2.0 s

Memory Limit: 256.0 MB

Description

Rayhan wants to give a special gift to his friends Abidur and Binoy. They both love beautiful arrays, where an array is called beautiful if it is sorted in non-decreasing order.

Rayhan has an array A of size n. He wants to create a new array B using the following rules:

1. In each move, he can remove either the first or the last element of array A.
2. He must insert the removed element either at the beginning or at the end of array B.

The goal is to make array B beautiful (non-decreasing) after all elements of A have been moved.
Determine if Rayhan can create such a beautiful array B for his friends.
Print "YES" if possible, otherwise print "NO".

Input

Each test contains multiple test cases. The first line contains the number of test cases
\(t (1 ≤ t ≤ 10^4)\). The description of the test cases follows.
The first line of each test case contains an integer \(n (1 ≤ n <= 10^5)\) the length of A.
The second line contains \(n\) integers \(A_1, A_2, ..., A_n (1 ≤ A_i ≤ 10^9)\) — the elements of array A.

It is guaranteed that the sum of n over all test cases does not exceed \(2*10^5\)

Output

For each test case, print "YES" if it is possible to create a beautiful array B, otherwise print "NO".

Sample

3
3
1 3 2
5
5 2 3 4 1
4
4 3 1 2

YES
NO
YES

Case 1: A = [1, 3, 2]
● Take 1 from the front of A and insert it back of B → B = [1], A = [3, 2].
● Take 2 from the back of A and insert it back of B → B = [1, 2], A = [3].
● Take 3 from the front of A and insert it back of B → B = [1, 2, 3], A = [].
Final B = [1, 2, 3] is sorted non-decreasing order → YES.
Case 3: A = [4, 3, 1, 2]
● Take 4 from the front of A and insert it back of B → B = [4], A = [3, 1, 2].
● Take 3 from the front of A and insert it in front of B → B = [3, 4], A = [1, 2].
● Take 2 from the back of A and insert it in front of B → B = [2, 3, 4], A = [1].
● Take 1 from the front of A and insert it in front of B → B = [1, 2, 3, 4], A = [].
Final B = [1, 2, 3, 4] is sorted non-decreasing order → YES.