GBU Programming club loves to play with arrays very much. One day they were thinking whether it is possible to sort an array in descending order in at most one operation by picking up an arbitrary number of elements from the beginning and putting it at last of the array.

You need to write a program that determines if it is possible to sort a given array or not.

Input

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

Output

For each test case, print a single line containing the string "YES" if it is possible to sort the array or "NO" if it is impossible.

Constraints

• 1 ≤ t ≤10⁹
• 1 ≤ n ≤10¹⁹
• 1 < A_i  < 10⁹