CF1604B.XOR Specia-LIS-t

YouKn0wWho has an integer sequence $a_1, a_2, \ldots a_n$. Now he will split the sequence $a$ into one or more consecutive subarrays so that each element of $a$ belongs to exactly one subarray. Let $k$ be the number of resulting subarrays, and $h_1, h_2, \ldots, h_k$ be the lengths of the longest increasing subsequences of corresponding subarrays.

For example, if we split $[2, 5, 3, 1, 4, 3, 2, 2, 5, 1]$ into $[2, 5, 3, 1, 4]$, $[3, 2, 2, 5]$, $[1]$, then $h = [3, 2, 1]$.

YouKn0wWho wonders if it is possible to split the sequence $a$ in such a way that the bitwise XOR of $h_1, h_2, \ldots, h_k$ is equal to $0$. You have to tell whether it is possible.

The longest increasing subsequence (LIS) of a sequence $b_1, b_2, \ldots, b_m$ is the longest sequence of valid indices $i_1, i_2, \ldots, i_k$ such that $i_1 \lt i_2 \lt \ldots \lt i_k$ and $b_{i_1} \lt b_{i_2} \lt \ldots \lt b_{i_k}$. For example, the LIS of $[2, 5, 3, 3, 5]$ is $[2, 3, 5]$, which has length $3$.

An array $c$ is a subarray of an array $b$ if $c$ can be obtained from $b$ by deletion of several (possibly, zero or all) elements from the beginning and several (possibly, zero or all) elements from the end.

YouKn0wWho 有一个整数序列 $a_1, a_2, \ldots, a_n$。现在他要将序列 $a$ 划分为一个或多个连续的子数组，使得 $a$ 中的每个元素恰好属于其中一个子数组。设划分后得到 $k$ 个子数组，且 $h_1, h_2, \ldots, h_k$ 分别为这些子数组的最长上升子序列（LIS）的长度。

例如，若将 $[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 想知道：是否存在一种划分方式，使得 $h_1, h_2, \ldots, h_k$ 的按位异或（bitwise XOR） 结果等于 $0$？你需要判断是否可行。

序列 $b_1, b_2, \ldots, b_m$ 的最长上升子序列（LIS） 是指满足如下条件的最长索引序列 $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]$ 的 LIS 是 $[2, 3, 5]$，其长度为 $3$。

若数组 $c$ 可通过从数组 $b$ 的开头删除若干（可能为零或全部）元素，并从结尾删除若干（可能为零或全部）元素而得到，则称 $c$ 是 $b$ 的一个子数组（subarray）。

The first line contains a single integer $t$ ($1 \le t \le 10\,000$) — the number of test cases.

The first line of each test case contains a single integer $n$ ($2 \le n \le 10^5$).

The second line of each test case contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le 10^9$).

It is guaranteed that the sum of $n$ over all test cases doesn't exceed $3 \cdot 10^5$.

第一行包含一个整数 $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$。

For each test case, print "YES" (without quotes) if it is possible to split into subarrays in the desired way, print "NO" (without quotes) otherwise. You can print each letter in any register (upper or lower).

对于每个测试用例，如果可以按要求将数组划分为若干子数组，则输出 "YES"（不带引号）；否则输出 "NO"（不带引号）。每个字母可使用任意大小写形式（大写或小写）。

In the first test case, YouKn0wWho can split the sequence in the following way: $[1, 3, 4]$, $[2, 2]$, $[1, 5]$. This way, the LIS lengths are $h = [3, 1, 2]$, and the bitwise XOR of the LIS lengths is $3 \oplus 1 \oplus 2 = 0$.

In the second test case, it can be shown that it is impossible to split the sequence into subarrays that will satisfy the condition.

在第一个测试用例中，YouKn0wWho 可以将序列如下分割：$[1, 3, 4]$、$[2, 2]$、$[1, 5]$。此时，各子数组的最长递增子序列（LIS）长度为 $h = [3, 1, 2]$，这些 LIS 长度的按位异或值为 $3 \oplus 1 \oplus 2 = 0$。

在第二个测试用例中，可以证明无法将该序列分割成满足条件的子数组。