P1410 Subsequence

Given a sequence of length $N$ (where $N$ is even), determine whether it can be partitioned into two strictly increasing subsequences, each of length $N / 2$.

Multiple lines, each line represents one set of testdata. For each set of testdata, first input an integer $N$, the length of the sequence. Then $N$ integers follow, representing the sequence.

The number of output lines is the same as the number of input lines. For each set of testdata, if such a partition exists, output `Yes!`, otherwise output `No!`.

**Constraints** There are three sets of testdata, each set contains at most $50$ lines, $0 \le$ all input numbers $\le 10^9$. Set 1 ($30\%$): $N \le 20$; Set 2 ($30\%$): $N \le 100$; Set 3 ($40\%$): $N \le 2000$. Translated by ChatGPT 5