1375C. C. Element Extermination

CF1375C. Element Extermination

时限: 1 秒 | 内存: 256 MB | 输入: 标准输入 | 输出: 标准输出

给定一个长度为 $n$ 的数组 $a$，该数组初始为 $1$ 到 $n$ 的一个排列。每次操作，你可以选择一个下标 $i$（$1 \leq i < n$），满足 $a_i < a_{i+1}$，然后从数组中移除 $a_i$ 或 $a_{i+1}$（移除后剩余部分拼接成新数组）。

例如，若数组为 $[1, 3, 2]$，你可以选择 $i = 1$（因为 $a_1 = 1 < a_2 = 3$），然后移除 $a_1$ 得到新数组 $[3, 2]$，或者移除 $a_2$ 得到新数组 $[1, 2]$。

请判断，是否可以通过若干次上述操作，将数组长度变为 $1$。

输入格式

第一行包含一个整数 $t$（$1 \leq t \leq 2 \times 10^4$），表示测试用例的数量。接下来是 $t$ 组测试数据。

每组测试数据的第一行包含一个整数 $n$（$2 \leq n \leq 3 \times 10^5$），表示数组的长度。

第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \leq a_i \leq n$，且 $a_i$ 两两不同），表示数组的元素。

保证所有测试用例中 $n$ 的总和不超过 $3 \times 10^5$。

输出格式

对于每个测试用例，若可以通过上述操作将数组缩减为只剩一个元素，输出一行 "YES"；否则输出 "NO"。

样例输入 1

4
3
1 2 3
4
3 1 2 4
3
2 3 1
6
2 4 6 1 3 5

样例输出 1

YES
YES
NO
YES

提示

对于前两个测试用例和第四个测试用例，可以按如下方式操作（加粗的元素为本次操作选择的一对）：

$[\text{1}, \textbf{2}, \textbf{3}] \rightarrow [\textbf{1}, \textbf{2}] \rightarrow [\text{1}]$

$[\text{3}, \textbf{1}, \textbf{2}, \text{4}] \rightarrow [\text{3}, \textbf{1}, \textbf{4}] \rightarrow [\textbf{3}, \textbf{4}] \rightarrow [\text{4}]$

$[\textbf{2}, \textbf{4}, \text{6}, \text{1}, \text{3}, \text{5}] \rightarrow [\textbf{4}, \textbf{6}, \text{1}, \text{3}, \text{5}] \rightarrow [\textbf{4}, \textbf{1}, \textbf{3}, \textbf{5}] \rightarrow [\textbf{4}, \textbf{1}, \textbf{5}] \rightarrow [\textbf{4}, \textbf{5}] \rightarrow [\text{4}]$