Triple Inversions Solution codechef

Triple Inversions Solution codechef

 

For a permutation P of the integers 1 to N, we define a new array AP of length N2 as follows:

  • For 1iN2, (AP)i denotes the number of inversions in the subarray P[i:i+2], i.e, the number of inversions in the array [Pi,Pi+1,Pi+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 AP=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 A1,A2,,AN.

Output Format

For each test case, output in a single line the answer — 𝚈𝙴𝚂if a permutation that satisfies the given conditions exists, and 𝙽𝙾 otherwise.

The output is not case sensitive, so for example the strings 𝚈𝙴𝚂, 𝚈𝚎𝚜, 𝚢𝙴𝚂, etc. will all be treated as correct.

Constraints

  • 1T105
  • 1N105
  • 0Ai3
  • The sum of N over all test cases doesn’t exceed 105

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=[1,2,6,5,3,4]. It can be verified that AP=[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 AP=[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

Leave a Comment