P9492 「SFCOI-3」Make a Split Solution

**Announcement: The Subtask 0 testdata was incorrect and has now been fixed.** ------------ Three-year-old Xiao Ming really dislikes complete things. He even wants to split sequences apart.

Given a sequence $a_1\dots a_n$, Xiao Ming wants to split it into two subsegments $[1, l]$ and $[l + 1, n]$ $(1 \leq l \lt n)$, i.e., $a_1\dots a_l$ and $a_{l+1}\dots a_n$. Because Xiao Ming is very obsessive, he does not want, for these two subsegments, one to be a **subsequence** of the other. In other words, he does not want one subsegment to be able to become the other by deleting some (possibly $0$) elements. When his parents are out, Xiao Ming finally finds a chance to split the sequence. So he wants to know whether there exists a way to split it such that neither subsegment is a subsequence of the other.

The first line contains an integer $T$, meaning Xiao Ming will split $T$ sequences in total. Then follow $T$ lines, each describing a sequence: + The first integer in each line is $n$, the length of the sequence. + The next $n$ integers are the elements of the sequence in order.

Output a total of $T$ lines. For each round, if there exists a split that satisfies the condition, output `YES`; otherwise output `NO`.

### Sample Explanation For the first sequence, all possible split methods are: - $\lbrace 1 \rbrace,\lbrace 2,1,2,1 \rbrace$. - $\lbrace 1,2 \rbrace,\lbrace 1,2,1 \rbrace$. - $\lbrace 1,2,1 \rbrace,\lbrace 2,1 \rbrace$. - $\lbrace 1,2,1,2 \rbrace,\lbrace 1 \rbrace$. Splitting at any position is invalid: the shorter sequence is always a subsequence of the other sequence. For the second sequence, one valid split is $\lbrace 1,2,1,1,2 \rbrace,\lbrace 1,0 \rbrace$. ### Constraints **This problem uses bundled testdata.** - Subtask 0 (15 points): $a_i = 0$. - Subtask 1 (15 points): $n = 10$, and the testdata is generated randomly. - Subtask 2 (30 points): $n$ is even. - Subtask 3 (40 points): No special constraints. For all testdata, $1\leq T \leq 10^5$, $2 \leq n \leq 10^5$, $1 \leq \sum n \leq 10^6$, $0 \leq a_i \leq 100$. Translated by ChatGPT 5