← 返回题目列表

Codeforces · 1375/C

C. 元素消灭

中文机器翻译题面 查看原题

给定一个长度为 $$$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 \cdot 10^4$$$) — 测试用例的数量。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$2 \leq n \leq 3 \cdot 10^5$$$) — 数组的长度。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1$$$, $$$a_2$$$, ..., $$$a_n$$$ ($$$1 \leq a_i \leq n$$$, $$$a_i$$$ 是成对不同的) — 数组的元素。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$3 \cdot 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 [\text{4}、\text{1}、\textbf{3}、 \textbf{5}] \rightarrow [\text{4}、\textbf{1}、\textbf{5}] \rightarrow [\textbf{4}、\textbf{5}] \rightarrow [\text{4}]$$$