## Number Arrangement NUART SOLUTIONS BRBG2020 Code Chef

Our chef is a teacher in a school named lobhabul Canadians.and there are N number of students numbered from 1 to N in his class. One day he decided to check the logical and thinking ability of his students by making them perform a fun activity. He told every student to write any number M and made them stand in a row.Let a1,a2 …an be the number chosen by students 1,2,3,…,N. Your task is to choose any two students standing at i and j location and interchange their position. You can perform this operation any number of times possibly zero times .such that after performing all operations, no three consecutive students should be having the same number. So, your task to tell whether it is possible to arrange the students in a row

Input:

The first line of the input contains a single integer t, denoting the number of test cases. The description of each test case follows.

The first line of every test case follows contains an integer N denoting the a total number of students.

The next line contains N space-separated integers a1,a2,….,an. Which denotes the number chosen by students from 1 to N.

Output:

For each test case, print a single line containing the string “YES” if all people can be arranged according to the rules of the chef or “NO” otherwise (without quotes)

Constraints

1≤T≤100

1≤N≤105

1≤a[i]≤109

The Sum of N over all test cases will be less than equal to 5 x 10^5

Sample Input:

2

9

2 2 2 2 2 2 2 2 2

5

1 2 1 2 3

Sample Output:

NO

YES

EXPLANATION:

In 1st case, since there is no way, such that no 3 students can have the same value. In the 2nd case, In the first step, we can swap the students standing at positions 3 and 5 having values 1 and 3 respectively. After 1st swap arrangement becomes 1 2 3 2 1 Now we can swap 4 and 5th student And our arrangement becomes 1 2 3 1 2 and here you can see no three consecutive students are having the same value.

**Contest Link:**

**https://www.codechef.com/BRBG2020/problems/NUART**