У вас есть два больших мешка с числами. Изначально первый мешок содержит \(n\) чисел: \(a_1, a_2, \ldots, a_n\), а второй мешок пуст. Вам разрешено применять следующие операции:
- Выбрать любое число из первого мешка и переместить его во второй мешок.
- Выбрать число из первого мешка, такое что равное ему обязательно присутствует во втором мешке, и увеличить его на единицу.
Вы можете применять неограниченное количество операций обоих типов в любом порядке. Возможно ли сделать содержимое первого и второго мешка одинаковым?
Выходные данные
Для каждого набора входных данных выведите «YES», если возможно уравнять содержимое мешков. Иначе выведите «NO».
Вы можете выводить каждую букву в любом регистре (например, «YES», «Yes», «yes», «yEs» будут распознаны как положительный ответ).
Примечание
Разберём шестой тестовый пример: покажем последовательность операций, приводящую к равенству мешков. Изначально первый мешок состоит из чисел \((3, 3, 4, 5, 3, 3)\), а второй мешок пуст.
- В первую операцию перемещаем число \(3\) из первого мешка во второй. Состояние: \((3, 4, 5, 3, 3)\) и \((3)\).
- Во вторую операцию увеличиваем число \(3\) из первого мешка на единицу. Эта операция возможна, так как второй мешок содержит число \(3\). Состояние: \((4, 4, 5, 3, 3)\) и \((3)\).
- В третью операцию перемещаем число \(4\) из первого мешка во второй. Состояние: \((4, 5, 3, 3)\) и \((3, 4)\).
- В четвёртую операцию увеличиваем число \(4\) из первого мешка на единицу. Состояние: \((5, 5, 3, 3)\) и \((3, 4)\).
- В пятую операцию перемещаем число \(5\) из первого мешка во второй. Состояние: \((5, 3, 3)\) и \((3, 4, 5)\).
- В шестую операцию увеличиваем число \(3\) из первого мешка на единицу. Состояние: \((5, 3, 4)\) и \((3, 4, 5)\).
Как видим, в результате таких операций возможно сделать содержимое мешков равным, поэтому ответ существует.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
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
|