D. A-B-C Сортировка
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам заданы три массива $$$a$$$, $$$b$$$ и $$$c$$$. Первоначально, массив $$$a$$$ состоит из $$$n$$$ элементов, массивы $$$b$$$ и $$$c$$$ — пустые.

Вы выполняете над ними следующий алгоритм, состоящий из двух шагов:

  • Шаг $$$1$$$: пока $$$a$$$ не пуст, вы забираете из $$$a$$$ последний элемент и перемещаете его в середину массива $$$b$$$. Если $$$b$$$ в данный момент нечетной длины, то вы сами можете выбрать: вставить число из $$$a$$$ слева или справа от центрального элемента в $$$b$$$. В результате $$$a$$$ станет пустым, а $$$b$$$ будет состоять из $$$n$$$ элементов.
  • Шаг $$$2$$$: пока $$$b$$$ не пуст, вы забираете из $$$b$$$ центральный элемент и перемещаете его в конец массива $$$c$$$. Если $$$b$$$ в данный момент четной длины, то вы сами можете выбрать какой из двух центральных элементов забрать. В результате $$$b$$$ станет пустым, а $$$c$$$ теперь состоит из $$$n$$$ элементов.
Обратитесь к Примечанию за примерами.

Можете ли вы получить отсортированный в порядке неубывания массив $$$c$$$?

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

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

В первой строке каждого набора задано одно целое число $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — длина массива $$$a$$$.

Во второй строке каждого набора заданы $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^6$$$) — сам массив $$$a$$$.

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

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

Для каждого набора входных данных, выведите YES (регистр не важен), если вы можете получить отсортированный по неубыванию массив $$$c$$$. В противном случае выведите NO (регистр не важен).

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

В первом наборе входных данных, мы можем сделать следующие преобразования массива $$$a = [3, 1, 5, 3]$$$:

Шаг $$$1$$$:

$$$a$$$$$$[3, 1, 5, 3]$$$$$$\Rightarrow$$$$$$[3, 1, 5]$$$$$$\Rightarrow$$$$$$[3, 1]$$$$$$\Rightarrow$$$$$$[3]$$$$$$\Rightarrow$$$$$$[]$$$
$$$b$$$$$$[]$$$$$$[\underline{3}]$$$$$$[3, \underline{5}]$$$$$$[3, \underline{1}, 5]$$$$$$[3, \underline{3}, 1, 5]$$$

Шаг $$$2$$$:

$$$b$$$$$$[3, 3, \underline{1}, 5]$$$$$$\Rightarrow$$$$$$[3, \underline{3}, 5]$$$$$$\Rightarrow$$$$$$[\underline{3}, 5]$$$$$$\Rightarrow$$$$$$[\underline{5}]$$$$$$\Rightarrow$$$$$$[]$$$
$$$c$$$$$$[]$$$$$$[1]$$$$$$[1, 3]$$$$$$[1, 3, 3]$$$$$$[1, 3, 3, 5]$$$
В результате массив $$$c = [1, 3, 3, 5]$$$ и он отсортирован.