# PROBLEM LINK:

Practice

Contest: Division 1

Contest: Division 2

Contest: Division 3

Contest: Division 4

* Author:* Arvind Khandelwal

*Takuki Kurokawa, Utkarsh Gupta*

**Testers:***Nishank Suresh*

**Editorialist:**# DIFFICULTY:

1018

# PREREQUISITES:

None

# PROBLEM:

Given an array A of 2N integers, can it be split into two arrays of length N, each containing distinct elements?

# EXPLANATION:

Suppose we split A into B and C, each containing distinct elements.

Consider some element x. x can appear at most once in B and at most once in C.

Of course, this means x can appear at most twice in A.

This applies to any integer, so *every* x must appear at most twice in A.

It’s not hard to see that this condition is also sufficient, i.e, splitting into B and C is possible *if and only if* no integer appears 3 or more times in A.

## Proof

If something appears 3 or more times, splitting is obviously impossible.

Suppose everything appears \leq 2 times.

For every element that appears twice, put one copy in B and one copy in C.

There are at most N such elements, so B and C both have length \leq N now.

The remaining elements can be distributed in any way to make B and C reach length N, since they will never break distinctness.

Checking this condition is fairly easy, and the constraints even allow for it to be done in \mathcal{O}(N^2):

- Fix an index i \ (1 \leq i \leq 2N)
- Run a loop over A to count the number of times A_i appears in A.
- If this count is \leq 2 for every i, the answer is
`Yes`

. Otherwise, the answer is`No`

.

# TIME COMPLEXITY

\mathcal{O}(N) per test case, or even \mathcal{O}(N^2) depending on implementation.

# CODE:

## Editorialist's code (Python)

```
for _ in range(int(input())):
n = int(input())
a = list(map(int, input().split()))
print('Yes' if max(a.count(x) for x in a) <= 2 else 'No')
```