E. Good Array
time limit per test
1.5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given an array $$$a$$$ of length $$$n$$$, and an initially empty array $$$b$$$.

You may perform the following operation at most once:

  1. Pick two arbitrary indices $$$l$$$ and $$$r$$$ ($$$1 \le l \le r \le n$$$).
  2. Replace $$$a_l, a_{l + 1}, \ldots, a_r$$$ with it's cyclic shift to the left by an offset of $$$1$$$.

For instance, choosing the indices $$$l = 2$$$ and $$$r = 5$$$ for the array $$$[1, 5, 2, 3, 4, 6]$$$ will result in the new array $$$[1, 2, 3, 4, 5, 6]$$$ after the operation is performed.

After performing the operation (if you choose to do so), you will build another array $$$b$$$ with the following process: on the $$$i$$$th turn of the process, you can insert $$$a_i$$$ at either the front or back of $$$b$$$.

Determine if there exists a way to construct $$$b$$$ such that $$$b$$$ is sorted in non-decreasing order after all $$$n$$$ elements are inserted.

Input

The first line contains a single integer $$$t$$$ ($$$1 \le t \le 4000$$$) — the number of test cases.

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 4000$$$) — the length of array $$$a$$$.

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — the array $$$a$$$.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$4000$$$.

Output

For each test case, print "YES" if there exists a way to construct $$$b$$$ such that it is sorted in non-decreasing order, or print "NO" if it is impossible. You can output the answer in any case (upper or lower). For example, the strings "yEs", "yes", "Yes", and "YES" will be recognized as positive responses.

Example
Input
3
6
1 5 2 3 4 6
6
1 3 2 4 5 4
7
6 12 4 9 4 9 15
Output
YES
NO
YES
Note

For the first test case, choose indices $$$l = 2$$$ and $$$r = 5$$$. Then the array becomes sorted, and inserting each element to the back of $$$b$$$ will result in $$$b$$$ being sorted.