Taco Rearrangement Problem

You are given several test cases. In each test case, you are given n problems with associated difficulty levels. Your task is to determine whether it is possible to rearrange the problems so that no two consecutive problems have the same difficulty level.

The key observation is that the rearrangement is possible if the most frequent difficulty appears at most \(\lceil \frac{n}{2} \rceil\) times. In other words, if we let \(m\) be the maximum frequency among the difficulties, then a valid rearrangement exists if and only if \(m \leq \lceil \frac{n}{2} \rceil\). Otherwise, output NO.

For each test case, output YES if a valid rearrangement exists; otherwise, output NO.

inputFormat

The input is read from standard input (stdin) and has the following format:

• The first line contains a single integer t, the number of test cases.
• For each test case:
• The first line contains an integer n, the number of problems.
• The second line contains n space-separated integers representing the difficulty levels of the problems.

outputFormat

For each test case, output a single line containing YES if it is possible to rearrange the problems so that no two consecutive problems have the same difficulty level, or NO if it is not possible. The output should be written to standard output (stdout).

## sample

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

YES
NO
YES

</p>