Задан массив целых чисел \(a\) длины \(n\). Элементы массива могут быть как различными, так и одинаковыми.
Каждый элемент массива покрашен либо в синий цвет, либо в красный. Непокрашенных элементов в массиве нет. За один ход разрешается применить к массиву одну из двух описанных ниже операций:
- либо выбрать любой синий элемент и уменьшить его значение на \(1\);
- либо выбрать любой красный элемент и увеличить его значение на \(1\).
Допустимы ситуации, в которых элементов некоторого цвета нет вообще. Например, если весь массив целиком покрашен в синий, или, наоборот, в красный. В таком случае первый (или второй, соответственно) способ сделать ход недоступен.
Определите, можно ли сделать \(0\) или более ходов так, чтобы в результате массив стал перестановкой чисел от \(1\) до \(n\)?
Иными словами, проверьте существует ли такая последовательность ходов (возможно, пустая), что после её применения массив \(a\) содержит в некотором порядке все числа от \(1\) до \(n\) (включительно), каждое ровно по одному разу.
Выходные данные
Выведите \(t\) строк, каждая из которых содержит ответ на соответствующий набор входных данных. В качестве ответа выведите YES, если соответствующий массив можно превратить в перестановку, и NO в противном случае.
Вы можете выводить ответ в любом регистре (например, строки yEs, yes, Yes и YES будут распознаны как положительный ответ).
Примечание
В первом наборе входных данных примера можно выполнить следующую последовательность ходов:
- выбрать \(i=3\), элемент \(a_3=5\) синий, поэтому уменьшим его, получим \(a=[1,2,4,2]\);
- выбрать \(i=2\), элемент \(a_2=2\) красный, поэтому увеличим его, получим \(a=[1,3,4,2]\);
- выбрать \(i=3\), элемент \(a_3=4\) синий, поэтому уменьшим его, получим \(a=[1,3,3,2]\);
- выбрать \(i=2\), элемент \(a_2=2\) красный, поэтому увеличим его, получим \(a=[1,4,3,2]\).
Получили, что \(a\) — перестановка. Следовательно, ответ YES.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
8
4
1 2 5 2
BRBR
2
1 1
BB
5
3 1 4 2 5
RBRRB
5
3 1 3 1 3
RBRRB
5
5 1 5 1 5
RBRRB
4
2 2 2 2
BRBR
2
1 -2
BR
4
-2 -1 4 0
RRRR
|
YES
NO
YES
YES
NO
YES
YES
YES
|