Problem Description

Consider a sequence $a_1, a_2, \dots, a_n$ of even length $n$. We call this sequence good if and only if there exists a partition of $a_1, a_2, \dots, a_n$ into two sets $U=\{ a_{i_1}, a_{i_2}, \dots, a_{i_{n/2}} \}$ and $V=\{ a_{j_1}, a_{j_2}, \dots, a_{j_{n/2}} \}=\{ a_1, a_2, \dots, a_n \}-U$, such that $i_1<i_2< \dots <i_{n/2}$, $a_{i_1}<a_{i_2}< \dots <a_{i_{n/2}}$, $j_1<j_2< \dots <j_{n/2}$, and $a_{j_1}<a_{j_2}< \dots <a_{j_{n/2}}$.

For example, the sequence $3, 1, 4, 5, 8, 7$ is a good sequence, because it can be split into $U=\{3, 4, 8\}$ and $V=\{1, 5, 7\}$. However, the sequence $3, 2, 1, 6, 5, 4$ is not a good sequence.

Now, for several given sequences, please determine whether each of them is a good sequence.

Input Format

The first line contains only one integer $m$, indicating that you need to judge $m$ sequences.
The next $m$ lines give these sequences. Each sequence is given on one line: the first number is an even integer $n$, indicating the length of the sequence, and the following $n$ integers are the elements of the sequence $a_1, a_2, \dots, a_n$. Numbers on the same line are separated by a single space.

Output Format

Output $m$ lines. If the $i$-th sequence is a good sequence, output Yes! on the $i$-th line; otherwise, output No!.

2
6 3 1 4 5 8 7
6 3 2 1 6 5 4

Yes!
No!

Hint

For $10\%$ of the testdata, $n \le 100$.
For $40\%$ of the testdata, $n \le 300$.
For $100\%$ of the testdata, $1 \le n \leq 2000$, $1 \le m \leq 25$, $0 \le a_i \le 10^6$.

Translated by ChatGPT 5