D. Отменённые развороты
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам дан массив $$$a$$$, состоящий из $$$n$$$ положительных целых чисел.

Для любого отрезка массива, начинающегося в позиции $$$l$$$ и заканчивающегося в позиции $$$r$$$ ($$$1 \le l \le r \le n$$$), пусть $$$m(l, r)$$$ обозначает минимальное значение на этом отрезке, а $$$M(l, r)$$$ — максимальное значение на этом отрезке. Формально,

$$$$$$ \begin{aligned} m(l,r) &= \min(a_l, a_{l+1}, \ldots, a_r),\\ M(l,r) &= \max(a_l, a_{l+1}, \ldots, a_r).\\ \end{aligned} $$$$$$

Вы можете выполнить следующую операцию любое количество раз (возможно, ноль):

  • выбрать два индекса $$$l$$$ и $$$r$$$ ($$$1 \le l \le r \le n$$$) так, что $$$m(l, r) + M(l, r)$$$ нечётно;
  • развернуть весь отрезок $$$a_l, a_{l+1}, \ldots, a_r$$$. Другими словами, для каждого $$$i$$$, такого что $$$l \le i \le r$$$, одновременно присвоить $$$a_i := a_{l+r-i}$$$.

Определите, можно ли сделать массив $$$a$$$ неубывающим$$$^{\text{∗}}$$$, выполнив некоторую последовательность операций.

$$$^{\text{∗}}$$$Массив $$$[b_1, b_2, \ldots, b_k]$$$ считается неубывающим тогда и только тогда, когда $$$b_1 \le b_2 \le \ldots \le b_k$$$.

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

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

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

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

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

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

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

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

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

Для первого набора входных данных массив уже является неубывающим. Поэтому ответ — YES.

Для второго набора входных данных выберем $$$l = 1$$$ и $$$r = 2$$$. Можно заметить, что $$$\min(2, 1) + \max(2, 1) = 2 + 1 = 3$$$, что нечётно. Следовательно, после одновременного присваивания $$$a_i := a_{3-i}$$$ для всех $$$1 \le i \le 2$$$ получим массив $$$a = [1, 2, 3]$$$, который является неубывающим.

Рассмотрим четвёртый набор входных данных:

  • Операция 1: выберем $$$l = 1$$$, $$$r = 3$$$. Массив станет равен $$$a = [2, 1, 4, 3, 3, 6]$$$.
  • Операция 2: выберем $$$l = 3$$$, $$$r = 5$$$. Массив станет равен $$$a = [2, 1, 3, 3, 4, 6]$$$.
  • Операция 3: выберем $$$l = 1$$$, $$$r = 2$$$. Массив станет равен $$$a = [1, 2, 3, 3, 4, 6]$$$.

Для пятого набора входных данных обратите внимание, что невозможно выбрать индексы $$$l$$$ и $$$r$$$, удовлетворяющие условиям. Поэтому ответ — NO.