P4728 [HNOI2009] Double Increasing Sequences

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

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 $m$ lines. If the $i$-th sequence is a good sequence, output `Yes!` on the $i$-th line; otherwise, output `No!`.

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