C. Синдзю и потерянная перестановка
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Синдзю очень любит перестановки! Сегодня она взяла перестановку $$$p$$$ у Дзюдзю, чтобы поиграть с ней.

$$$i$$$-й циклический сдвиг перестановки $$$p$$$ — это такое преобразование, что перестановка $$$p = [p_1, p_2, \ldots, p_n] $$$ становится равной $$$ p = [p_{n-i+1}, \ldots, p_n, p_1,p_2, \ldots, p_{n-i}]$$$.

Назовём мощностью перестановки $$$p$$$ количество различных элементов в массиве префиксных максимумов $$$b$$$. Массив префиксных максимумов $$$b$$$ — это массив длины $$$n$$$, в котором $$$b_i = \max(p_1, p_2, \ldots, p_i)$$$. Например, мощность перестановки $$$[1, 2, 5, 4, 6, 3]$$$ равна $$$4$$$, так как $$$b=[1,2,5,5,6,6]$$$ и в $$$b$$$ всего $$$4$$$ различных элемента.

К сожалению, Синдзю потеряла перестановку $$$p$$$! Вся информация, которую она помнит — это массив $$$c$$$, где $$$c_i$$$ равно мощности $$$(i-1)$$$-го циклического сдвига перестановки $$$p$$$. Она не уверена, что запомнила всё правильно, теперь она хочет проверить свою память.

Задан массив $$$c$$$, определите, существует ли такая перестановка $$$p$$$, которая согласуется с заданным массивом $$$c$$$. Вам не нужно находить саму перестановку $$$p$$$.

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

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

Входные данные состоят из одного или нескольких наборов входных данных. Первая строка содержит целое число $$$t$$$ ($$$1 \leq t \leq 5 \cdot 10^3$$$) — количество наборов входных данных.

Первая строка каждого набора входных данных содержит целое число $$$n$$$ ($$$1 \le n \le 10^5$$$).

Во второй строке каждого набора входных данных записаны $$$n$$$ целых чисел $$$c_1,c_2,\ldots,c_n$$$ ($$$1 \leq c_i \leq n$$$).

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

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

Для каждого набора входных выведите «YES», если существует перестановка $$$p$$$, согласующаяся с заданным массивом $$$c$$$. Выведите «NO» в противном случае.

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

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

В первом наборе входных данных примера перестановка $$$[1]$$$ согласуется с заданным массивом $$$c$$$.

Во втором наборе входных данных примера перестановка $$$[2,1]$$$ согласуется с заданным массивом $$$c$$$.

В пятом наборе входных данных примера перестановка $$$[5,1,2,4,6,3]$$$ согласуется с заданным массивом $$$c$$$, так как:

  • нулевой циклический сдвиг перестановки $$$p$$$ — это $$$[5, 1, 2, 4, 6, 3]$$$. Мощность этого сдвига равна $$$2$$$, так как $$$b = [5, 5, 5, 5, 6, 6]$$$, в этом массиве только $$$2$$$ различных элемента: $$$5$$$ и $$$6$$$.
  • первый циклический сдвиг перестановки $$$p$$$ это $$$[3, 5, 1, 2, 4, 6]$$$. Мощность этого сдвига равна $$$3$$$, так как $$$b=[3,5,5,5,5,6]$$$.
  • второй циклический сдвиг перестановки $$$p$$$ это $$$[6, 3, 5, 1, 2, 4]$$$. Мощность этого сдвига равна $$$1$$$, так как $$$b=[6,6,6,6,6,6]$$$.
  • третий циклический сдвиг перестановки $$$p$$$ это $$$[4, 6, 3, 5, 1, 2]$$$. Мощность этого сдвига равна $$$2$$$, так как $$$b=[4,6,6,6,6,6]$$$.
  • четвёртый циклический сдвиг перестановки $$$p$$$ это $$$[2, 4, 6, 3, 5, 1]$$$. Мощность этого сдвига равна $$$3$$$, так как $$$b = [2, 4, 6, 6, 6, 6]$$$.
  • пятый циклический сдвиг перестановки $$$p$$$ это $$$[1, 2, 4, 6, 3, 5]$$$. Мощность этого сдвига равна $$$4$$$, так как $$$b = [1, 2, 4, 6, 6, 6]$$$.

Таким образом, для этой перестановки $$$c = [2, 3, 1, 2, 3, 4]$$$.

В третьем, четвёртом и шестом наборах входных данных примера можно показать, что искомой перестановки, которая согласуется с $$$c$$$, не существует.