Rearrange Array Challenge

Given an array of integers, determine if it is possible to rearrange it so that no two adjacent elements are equal. For an array of length (n), let the maximum frequency of any element be (max_freq). A valid rearrangement is possible if and only if (max_freq \leq \lceil \frac{n}{2} \rceil). Otherwise, it is impossible to avoid adjacent duplicates. Your task is to process multiple test cases and output, for each, whether such a rearrangement can be achieved.

inputFormat

The input is read from standard input. The first line contains an integer (T) indicating the number of test cases. For each test case, the first line contains an integer (n) denoting the number of elements in the array. The next line contains (n) space-separated integers representing the array elements.

outputFormat

For each test case, print a single line containing either "Yes" if a valid rearrangement is possible or "No" if it is not.## sample

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

Yes
Yes
No