B. Специа-LIS-т по XOR
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У YouKn0wWho есть последовательность целых чисел $$$a_1, a_2, \ldots a_n$$$. Он собирается разбить последовательность $$$a$$$ на один или несколько последовательных подмассивов так, чтобы каждый элемент $$$a$$$ принадлежал ровно одному подмассиву. Пусть $$$k$$$ — количество получившихся подмассивов, а $$$h_1, h_2, \ldots, h_k$$$ — длины самых наибольших возрастающих подпоследовательностей соответствующих подмассивов.

Например, если разделить $$$[2, 5, 3, 1, 4, 3, 2, 2, 5, 1]$$$ на $$$[2, 5, 3, 1, 4]$$$, $$$[3, 2, 2, 5]$$$, $$$[1]$$$, то $$$h = [3, 2, 1]$$$.

YouKn0wWho интересуется, можно ли разделить последовательность $$$a$$$ так, чтобы побитовое исключающее ИЛИ чисел $$$h_1, h_2, \ldots, h_k$$$ было равно $$$0$$$. Вы должны сказать, возможно ли это.

Наибольшая возрастающая подпоследовательность (НВП, LIS) последовательности $$$b_1, b_2, \ldots, b_m$$$ — это самая длинная последовательность индексов $$$i_1, i_2, \ldots, i_k$$$ таких, что $$$i_1 \lt i_2 \lt \ldots \lt i_k$$$ и $$$b_{i_1} \lt b_{i_2} \lt \ldots \lt b_{i_k}$$$. Например, НВП массива $$$[2, 5, 3, 3, 5]$$$ — это $$$[2, 3, 5]$$$, которая имеет длину $$$3$$$.

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

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

Первая строка содержит одно целое число $$$t$$$ ($$$1 \le t \le 10\,000$$$)  — количество наборов входных данных.

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

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

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

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

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

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

В первом наборе входных данных YouKn0wWho может разделить последовательность следующим образом: $$$[1, 3, 4]$$$, $$$[2, 2]$$$, $$$[1, 5]$$$. Таким образом, длины НВП будут $$$h = [3, 1, 2]$$$, а побитовое исключающее ИЛИ длин НВП будет $$$3 \oplus 1 \oplus 2 = 0$$$.

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