Rearrange Array to Avoid Consecutive Duplicates

You are given an array of integers. Your task is to determine whether it is possible to rearrange the elements of the array such that no two adjacent elements are identical.

More formally, given an array \(A\) of length \(n\), you need to check if there exists a permutation \(P\) of \(A\) such that for every \(1 \leq i < n\), \(P[i] \neq P[i+1]\). A necessary and sufficient condition for such a rearrangement to exist is that the maximum frequency \(f_{max}\) of any element does not exceed \(\lceil \frac{n}{2} \rceil\), i.e., \[ f_{max} \leq \left\lceil \frac{n}{2} \right\rceil. \] If this condition holds, output Yes; otherwise, output No.

The input consists of multiple test cases. For each test case, you will be given the number of elements in the array followed by the array elements themselves. Process each test case independently and output the result for each on a new line.

inputFormat

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

• The first line contains an integer \(n\), the number of elements in the array.
• The second line contains \(n\) space-separated integers representing the elements of the array.

Read the input from stdin.

outputFormat

For each test case, output a single line containing either Yes if a valid rearrangement exists, or No if it does not. Write your answer to stdout.

## sample

1
5
1 2 3 4 5

Yes

</p>