Rearranging Books Without Adjacent Same Genres

You are given a collection of books, each with a genre represented by an integer. The task is to determine whether it is possible to rearrange the books so that no two consecutive books have the same genre.

For each test case, you are given an integer \( n \) representing the number of books and a list of \( n \) integers where each integer indicates the genre of a book. A valid rearrangement exists if the maximum frequency \( f_{max} \) of any genre satisfies the condition \[ f_{max} \le \left\lceil \frac{n}{2} \right\rceil, \] where \( \lceil \cdot \rceil \) denotes the ceiling function. If the condition holds, output "YES"; otherwise, output "NO".

Input and Output

The input and output are handled via standard input and output channels respectively.

inputFormat

The first line of input contains a single integer \( T \) representing the number of test cases. The following lines describe each test case:

• For each test case, the first line contains an integer \( n \) representing the number of books.
• The next line contains \( n \) space-separated integers, where each integer represents a genre label.

outputFormat

For each test case, print a single line containing either "YES" if the books can be rearranged so that no two adjacent books share the same genre, or "NO" otherwise.

## sample

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

YES
NO
YES

</p>