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

Вам дана перестановка$$$^{\text{∗}}$$$ $$$p$$$ длины $$$n$$$.

Вы должны выполнить ровно одну операцию для каждого целого числа $$$k$$$ от 1 до $$$n$$$ по порядку:

  • Выберите подмассив$$$^{\text{†}}$$$ $$$p$$$ длиной ровно $$$k$$$ и вычтите 1 из каждого элемента в этом подмассиве.

После завершения всех $$$n$$$ операций ваша цель — сделать так, чтобы все элементы массива стали равны нулю.

Определите, возможно ли это.

$$$^{\text{∗}}$$$Перестановкой длины $$$n$$$ является массив, состоящий из $$$n$$$ различных целых чисел от $$$1$$$ до $$$n$$$ в произвольном порядке. Например, $$$[2,3,1,5,4]$$$ — перестановка, но $$$[1,2,2]$$$ не перестановка ($$$2$$$ встречается в массиве дважды) и $$$[1,3,4]$$$ тоже не перестановка ($$$n=3$$$, но в массиве встречается $$$4$$$).

$$$^{\text{†}}$$$Массив $$$a$$$ является подмассивом массива $$$b$$$, если $$$a$$$ может быть получен из $$$b$$$ удалением нескольких (возможно, ни одного или всех) элементов с начала и нескольких (возможно, ни одного или всех) элементов с конца.

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

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

Первая строка каждого набора входных данных содержит одно число $$$n$$$ ($$$1 \leq n \leq 100$$$) — длину перестановки.

Вторая строка содержит $$$p_1, p_2, \ldots p_n$$$ ($$$1 \le p_i \le n$$$) — саму перестановку.

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

Для каждого набора входных данных выведите YES, если возможно сделать все элементы массива $$$p$$$ равными $$$0$$$ после выполнения всех операций; в противном случае выведите NO.

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

Пример
Входные данные
4
4
1 3 4 2
5
1 5 2 4 3
5
2 4 5 3 1
3
3 1 2
Выходные данные
YES
NO
YES
NO
Примечание

Для первого набора входных данных мы можем действовать следующим образом:

  • $$$k = 1$$$: Выберите подмассив $$$[3, 3]$$$. Массив $$$[1, 3, 4, 2]$$$ становится $$$[1, 3, 3, 2]$$$.
  • $$$k = 2$$$: Выберите подмассив $$$[2, 3]$$$. Массив $$$[1, 3, 3, 2]$$$ становится $$$[1, 2, 2, 2]$$$.
  • $$$k = 3$$$: Выберите подмассив $$$[2, 4]$$$. Массив $$$[1, 2, 2, 2]$$$ становится $$$[1, 1, 1, 1]$$$.
  • $$$k = 4$$$: Выберите подмассив $$$[1, 4]$$$. Массив $$$[1, 1, 1, 1]$$$ становится $$$[0, 0, 0, 0]$$$.

Таким образом, мы успешно уменьшили весь массив до нулей, поэтому ответ YES.

Для второго набора входных данных можно показать, что невозможно уменьшить все элементы до нуля.

Для третьего набора входных данных процесс выглядит следующим образом:

$$$[2, 4, \boldsymbol{5}, 3, 1] \rightarrow [2, \boldsymbol{4, 4}, 3, 1] \rightarrow [2, \boldsymbol{3, 3, 3}, 1] \rightarrow [\boldsymbol{2, 2, 2, 2}, 1] \rightarrow [\boldsymbol{1, 1, 1, 1, 1}] \rightarrow [0, 0, 0, 0, 0].$$$

Выделенные значения указывают на подмассивы, из которых мы вычитаем на каждом шаге.

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