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

Среди людей из города GR ходит легенда о горке, которая ведет в закулисье. Массив $$$b$$$, состоящий из $$$m$$$ целых чисел, называется горкой, если существует индекс $$$k$$$ ($$$1\le k\le m$$$) такой, что выполняются следующие условия:

  • Первые $$$k$$$ элементов возрастают. Формально, для всех $$$i$$$ ($$$1\le i\lt k$$$) выполняется $$$b_i\lt b_{i+1}$$$.
  • Последние $$$m-k+1$$$ элементов убывают. Формально, для всех $$$i$$$ ($$$k\le i\lt m$$$) выполняется $$$b_i\gt b_{i+1}$$$.

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

  • Выберите любой индекс $$$i$$$ ($$$1\le i\le n-2$$$).
  • Поменяйте местами $$$a_i$$$ и $$$a_{i+2}$$$ в массиве.

Ваша задача — определить, возможно ли превратить массив $$$a$$$ в горку, делая произвольное количество операций.

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

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

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

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

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

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

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

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

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

В первом наборе входных данных массив $$$a$$$ невозможно превратить в горку.

Во втором наборе входных данных массив $$$a$$$ уже является горкой.

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

  • Поменяйте местами $$$a_1$$$ и $$$a_3$$$. После этой операции массив $$$a$$$ станет $$$[4, 3, 5, 6, 2, 1]$$$.
  • Поменяйте местами $$$a_2$$$ и $$$a_4$$$. После этой операции массив $$$a$$$ станет $$$[4, 6, 5, 3, 2, 1]$$$.
И массив $$$[4, 6, 5, 3, 2, 1]$$$ является горкой.