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$$$。你必须告诉它是否可能。
序列 $$$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$$$ 获得。
输入
第一行包含一个整数 $$$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”(不带引号)。您可以打印任何寄存器(上部或下部)中的每个字母。
示例
输入 #1
4 7 1 3 4 2 2 1 5 3 1 3 4 5 1 3 2 4 2 4 4 3 2 1
输出 #1
YES NO YES YES
注意
在第一个测试用例中,YouKn0wWho 可以通过以下方式拆分序列:$$$[1, 3, 4]$$$、$$$[2, 2]$$$、$$$[1, 5]$$$。这样,LIS 长度为 $$$h = [3, 1, 2]$$$,LIS 长度的按位异或为 $$$3 \oplus 1 \oplus 2 = 0$$$。
在第二个测试用例中,可以证明不可能将序列分割成满足条件的子数组。