## GUPTA MECHANICAL

IN THIS WEBSITE I CAN TELL ALL ABOUT TECH. TIPS AND TRICKS APP REVIEWS AND UNBOXINGS ALSO TECH. NEWS .............

## Triple Inversions CodeChef Solution | CodeChef Problem Solution 2022

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\le i\le N-2$$\left({A}_{P}{\right)}_{i}$ denotes the number of inversions in the subarray $P\left[i:i+2\right]$, i.e, the number of inversions in the array $\left[{P}_{i},{P}_{i+1},{P}_{i+2}\right]$.

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},\dots ,{A}_{N}$.

### Output Format

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

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

### Constraints

• $1\le T\le {10}^{5}$
• $1\le N\le {10}^{5}$
• $0\le {A}_{i}\le 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

Test case $1$: Consider $P=\left[1,2,6,5,3,4\right]$. It can be verified that ${A}_{P}=\left[0,1,3,2\right]$. There are other permutations which give the same array — for example $\left[2,3,6,5,1,4\right]$ and $\left[3,4,6,5,1,2\right]$.

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

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

Test case $4$: It can be verified that no permutation $P$ of length $7$ has