Description

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$.

Input Format

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.

Output Format

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!.

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

Yes!
No!

Hint

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