Performer Parade Arrangement

In this problem, you are given a list of performers each with a certain skill level. Your task is to determine if it is possible to arrange the performers in a parade such that no two adjacent performers have the same skill level. This is equivalent to checking if the maximum frequency of any skill level does not exceed (\lceil \frac{N}{2} \rceil), where (N) is the total number of performers.

For example, if the performers' skill levels are [1, 2, 3, 2, 1], a valid arrangement exists so the answer is "YES". However, if all performers have the same skill level (for example, [1, 1, 1, 1]), it is impossible to arrange them without two identical adjacent performers, and the answer is "NO".

inputFormat

The first line of the input contains an integer (T) representing the number of test cases. Each test case consists of a single line containing an integer (N) (the number of performers) followed by (N) integers, representing the skill levels of the performers. All values are space-separated.

outputFormat

For each test case, output a single line with the answer "YES" if the performers can be arranged such that no two adjacent performers have the same skill level, otherwise output "NO".## sample

3
5 1 2 3 2 1
4 1 1 1 1
6 1 2 3 4 5 6

YES
NO
YES