Background

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.

Problem Description

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.

Input Format

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 Format

Output a total of $T$ lines.

For each round, if there exists a split that satisfies the condition, output YES; otherwise output NO.

2
5 1 2 1 2 1
7 1 2 1 1 2 1 0

NO
YES

Hint

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