B. Два больших мешка
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У вас есть два больших мешка с числами. Изначально первый мешок содержит $$$n$$$ чисел: $$$a_1, a_2, \ldots, a_n$$$, а второй мешок пуст. Вам разрешено применять следующие операции:

  • Выбрать любое число из первого мешка и переместить его во второй мешок.
  • Выбрать число из первого мешка, такое что равное ему обязательно присутствует во втором мешке, и увеличить его на единицу.

Вы можете применять неограниченное количество операций обоих типов в любом порядке. Возможно ли сделать содержимое первого и второго мешка одинаковым?

Входные данные

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит целое число $$$n$$$ ($$$2 \le n \le 1000$$$) — длина массива $$$a$$$. Гарантируется, что $$$n$$$ — чётное число.

Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le n$$$).

Гарантируется, что сумма значений $$$n^2$$$ по всем наборам входных данных не превосходит $$$10^6$$$.

Выходные данные

Для каждого набора входных данных выведите «YES», если возможно уравнять содержимое мешков. Иначе выведите «NO».

Вы можете выводить каждую букву в любом регистре (например, «YES», «Yes», «yes», «yEs» будут распознаны как положительный ответ).

Пример
Входные данные
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
Выходные данные
Yes
No
Yes
Yes
No
Yes
No
Yes
Yes
Примечание

Разберём шестой тестовый пример: покажем последовательность операций, приводящую к равенству мешков. Изначально первый мешок состоит из чисел $$$(3, 3, 4, 5, 3, 3)$$$, а второй мешок пуст.

  1. В первую операцию перемещаем число $$$3$$$ из первого мешка во второй. Состояние: $$$(3, 4, 5, 3, 3)$$$ и $$$(3)$$$.
  2. Во вторую операцию увеличиваем число $$$3$$$ из первого мешка на единицу. Эта операция возможна, так как второй мешок содержит число $$$3$$$. Состояние: $$$(4, 4, 5, 3, 3)$$$ и $$$(3)$$$.
  3. В третью операцию перемещаем число $$$4$$$ из первого мешка во второй. Состояние: $$$(4, 5, 3, 3)$$$ и $$$(3, 4)$$$.
  4. В четвёртую операцию увеличиваем число $$$4$$$ из первого мешка на единицу. Состояние: $$$(5, 5, 3, 3)$$$ и $$$(3, 4)$$$.
  5. В пятую операцию перемещаем число $$$5$$$ из первого мешка во второй. Состояние: $$$(5, 3, 3)$$$ и $$$(3, 4, 5)$$$.
  6. В шестую операцию увеличиваем число $$$3$$$ из первого мешка на единицу. Состояние: $$$(5, 3, 4)$$$ и $$$(3, 4, 5)$$$.

Как видим, в результате таких операций возможно сделать содержимое мешков равным, поэтому ответ существует.