Two Large Bags
Contest: Codeforces Round 1004 (Div. 2)
Difficulty rating: 1200
Tags: brute force, dp, greedy, sortings

You have two large bags of numbers. Initially, the first bag contains $$$n$$$ numbers: $$$a_1, a_2, \ldots, a_n$$$, while the second bag is empty. You are allowed to perform the following operations:

- Choose any number from the first bag and move it to the second bag.
- Choose a number from the first bag that is also present in the second bag and increase it by one.

You can perform an unlimited number of operations of both types, in any order. Is it possible to make the contents of the first and second bags identical?

Input format:
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). The description of the test cases follows.

The first line of each test case contains an integer $$$n$$$ ($$$2 \le n \le 1000$$$) — the length of the array $$$a$$$. It is guaranteed that $$$n$$$ is an even number.

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le n$$$).

It is guaranteed that the sum of $$$n^2$$$ over all test cases does not exceed $$$10^6$$$.

Output format:
For each test case, print "YES" if it is possible to equalize the contents of the bags. Otherwise, output "NO".

You can output each letter in any case (for example, "YES", "Yes", "yes", "yEs", "yEs" will be recognized as a positive answer).

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
Let's analyze the sixth test case: we will show the sequence of operations that leads to the equality of the bags. Initially, the first bag consists of the numbers $$$(3, 3, 4, 5, 3, 3)$$$, and the second bag is empty.

1. In the first operation, move the number $$$3$$$ from the first bag to the second. State: $$$(3, 4, 5, 3, 3)$$$ and $$$(3)$$$.
2. In the second operation, increase the number $$$3$$$ from the first bag by one. This operation is possible because the second bag contains the number $$$3$$$. State: $$$(4, 4, 5, 3, 3)$$$ and $$$(3)$$$.
3. In the third operation, move the number $$$4$$$ from the first bag to the second. State: $$$(4, 5, 3, 3)$$$ and $$$(3, 4)$$$.
4. In the fourth operation, increase the number $$$4$$$ from the first bag by one. State: $$$(5, 5, 3, 3)$$$ and $$$(3, 4)$$$.
5. In the fifth operation, move the number $$$5$$$ from the first bag to the second. State: $$$(5, 3, 3)$$$ and $$$(3, 4, 5)$$$.
6. In the sixth operation, increase the number $$$3$$$ from the first bag by one. State: $$$(5, 3, 4)$$$ and $$$(3, 4, 5)$$$.

As we can see, as a result of these operations, it is possible to make the contents of the bags equal, so the answer exists.

Example input:
9
2
1 1
2
2 1
4
1 1 4 4
4
3 4 3 3
4
2 3 4 4
6
3 3 4 5 3 3
6
2 2 2 4 4 4
8
1 1 1 1 1 1 1 4
10
9 9 9 10 10 10 10 10 10 10

Example output:
Yes
No
Yes
Yes
No
Yes
No
Yes
Yes

Editorial:
Note that when a number goes into the second bag, it remains unchanged there until the end of the entire process: our operations cannot interact with this number in any way.
Therefore, every time we send a number to the second bag, we must keep in mind that an equal number must remain in the first bag by the end of the operations if we want to equalize the contents of the bags. We will call this equal number in the first bag "blocked": as no operations should be performed with it anymore.
Let's sort the array: $$$a_1 \leq a_2 \leq \ldots \leq a_n$$$.
The first action we will take: sending one of the numbers to the second bag, since the second bag is empty at the beginning of the operations, which means the second operation is not available.
We will prove that at some point we will definitely want to send a number equal to $$$a_1$$$ to the second bag. Proof by contradiction. Suppose we never do this. Then all the numbers in the second bag, at the end of the operations, will be $$$>a_1$$$. And the number $$$a_1$$$ will remain in the first bag, which cannot be increased if we never sent $$$a_1$$$ to the second bag. Thus, the contents of the bags will never be equal if we do not send the number $$$a_1$$$ to the second bag. Therefore, during the operations, we must do this. And we can do this as the first operation since operations with numbers $$$>a_1$$$ do not interact with $$$a_1$$$ in any case.
Alright, our first move: transfer $$$a_1$$$ to the second bag. Now we need to "block" one copy of the number $$$a_1$$$ in the first bag and not use it in further operations. Therefore, if $$$a_2 > a_1$$$, we instantly lose. Otherwise, we fix $$$a_2=a_1$$$ in the first bag and $$$a_1$$$ in the second bag.
And we return to the original problem, but now with the numbers $$$a_3, a_4, \ldots, a_n$$$. However, now we have the number $$$=a_1$$$ in the second bag. This means that now, perhaps, the first action should not be to transfer the minimum to the second bag, but to somehow use the second operation.
It turns out that it is always optimal to use the second operation when possible, not counting the "blocked" numbers. That is, to increase all equal $$$a_1$$$ numbers in the first bag by one. And then proceed to the same problem, but with a reduced $$$n$$$.
Why is this so? Suppose we leave some equal $$$a_1$$$ numbers in the first bag without increasing them. Then, by the same logic, we must transfer one of them to the second bag, blocking the equal number in the first bag. But the same could be done if we increased both numbers by $$$1$$$, they would still be equal, and there would still be the option to transfer one of them to the second bag and block the equal one in the first. Moreover, the number equal to $$$a_1$$$ is already in the second bag, so adding a second copy does not expand the arsenal of possible operations in any way. Therefore, it is never worse to add one to all remaining $$$=a_1$$$ numbers. And proceed to the problem with the array $$$a_3,a_4,\ldots,a_n$$$, where all numbers are $$$>a_1$$$, which can already be solved similarly.
A naive simulation of this process takes $$$O(n^2)$$$, but, of course, it can be handled in $$$O(n \log n)$$$ without much effort, and if we sort the array using counting sort, it can be done in $$$O(n)$$$ altogether.