For a [permutation] P of the integers 1 to N, we define a new array A_{P} of length N-2 as follows:

For 1 ≤ i ≤ N-2, (A_{P})i denotes the number of [inversions] in the subarray P[i : i+2], i.e, the number of inversions in the array [P].}, P_{i+1}, P_{i+2

You are given an array A of length N, all of whose elements lie between 0 and 3. Does there exist a permutation P of length N+2 such that A_{P} = A?

------ Input Format ------

• The first line of input will contain one integer T, the number of test cases. The description of T test cases follows.
• Each test case consists of two lines of input.
• The first line of each test case contains a single integer N, the size of A.
• The second line of each test case contains N space-separated integers — the values of $A_{1}, A_{2}, \ldots, A_{N}$.

------ Output Format ------

For each test case, output in a single line the answer — $\texttt{YES}$ if a permutation that satisfies the given conditions exists, and $\texttt{NO}$ otherwise.

The output is not case sensitive, so for example the strings $\texttt{YES, Yes, yES},$ etc. will all be treated as correct.

------ Constraints ------

$1 ≤ T ≤ 10^{5}$
$1 ≤ N ≤ 10^{5}$
$0 ≤ A_{i} ≤ 3$
- The sum of $N$ over all test cases doesn't exceed $10^{5}$

----- Sample Input 1 ------
4
4
0 1 3 2
4
0 1 2 3
4
0 0 0 0
5
0 1 2 1 0
----- Sample Output 1 ------
YES
NO
YES
NO
----- explanation 1 ------
Test case $1$: Consider $P = [1, 2, 6, 5, 3, 4]$. It can be verified that $A_{P} = [0, 1, 3, 2]$. There are other permutations which give the same array — for example $[2, 3, 6, 5, 1, 4]$ and $[3, 4, 6, 5, 1, 2]$.

Test case $2$: It can be verified that no permutation $P$ of length $6$ has $A_{P} = [0, 1, 2, 3]$.

Test case $3$: The only permutation that satisfies the condition is $P = [1, 2, 3, 4, 5, 6]$.

Test case $4$: It can be verified that no permutation $P$ of length $7$ has $A_{P} = [0, 1, 2, 1, 0]$

见题面

见题面