Equal MEX solution|codesheff starter 25 for div 3

The MEX (minimum excluded) of an array is the smallest non-negative integer that does not belong to the array. For instance:

• The MEX of [2,2,1]$[2,2,1]$ is 0$0$ because 0$0$ does not belong to the array.
• The MEX of [3,1,0,1]$[3,1,0,1]$ is 2$2$ because 0$0$ and 1$1$ belong to the array, but 2$2$ does not.
• The MEX of [0,3,1,2]$[0,3,1,2]$ is 4$4$ because 0,1,2$0,1,2$ and 3$3$ belong to the array, but 4$4$ does not.

You're given an array A$A$ containing 2⋅N$2\cdot N$ integers where 0≤Ai≤N$0\le A_i\le N$. Is it possible to reorder the elements of the array in such a way that the MEX of the first N$N$ elements is equal to the MEX of the last N$N$ elements?

Input Format

• The first line contains T$T$ denoting the number of test cases. Then the test cases follow.
• The first line of each test case contains a single integer N$N$.
• The second line contains 2⋅N$2\cdot N$ space-separated integers A1,A2,…,A2⋅N$A_1,A_2,\dots ,A_{2\cdot N}$.

Output Format

For each test case, print YES if there is a valid reordering of the given array and NO otherwise.

You may print each character of the string in uppercase or lowercase (for example, the strings "yEs", "yes", "Yes" and "YES" will all be treated as identical).

Constraints

• 1≤T≤104$1\le T\le {10}^4$
• 1≤N≤105$1\le N\le {10}^5$
• 0≤Ai≤N$0\le A_i\le N$
• Sum of N$N$ over all test cases does not exceed 2⋅105$2\cdot {10}^5$.

Sample Input 1 

4
2
0 0 0 1
2
0 0 1 1
3
1 3 2 3 3 2
3
0 0 1 1 1 2

Sample Output 1 

NO
YES
YES
NO

Explanation

Test case 1$1$: There is no way to reorder the elements of the array [0,0,0,1]$[0,0,0,1]$ which satisfies the given conditions.

Test case 2$2$: One possible reordering is [0,1,0,1]$[0,1,0,1]$. Here the MEX of the first half is MEX([0,1])=2$([0,1])=2$ and the MEX of the second half is MEX([0,1])=2$([0,1])=2$.

Test case 3$3$: The given array already satisfies the conditions. Here the MEX of the first half is MEX([1,3,2])=0$([1,3,2])=0$ and the MEX of the second half is MEX([3,3,2])=0$([3,3,2])=0$

Solution:

click here for solution