410275: GYM103999 D Gioconda

While searching in the garbage cans, Jean found a sequence of $$$N$$$ positive integers. Because he has no use for this, he gifted it to Nicusor Gioconda, and gave him a challenge too.

Nicusor has to chose pairwise distinct substrings of length $$$2$$$ such that every index is taken at least once. If he will give a correct partitioning, he will get the ultimate prize: the magical chicken wing!

In this problem, we consider that a substring is a contiguous subset of indices $$$[i,i+1,\cdots j-1, j]$$$.

Because he is far better at singing than he is at solving problems, he asks for your help.

First line will contain a single number $$$N$$$ ($$$1 \leq N \leq 10^5$$$) - the length of the sequence. The next line contains a sequence $$$A$$$ of $$$N$$$ positive values ($$$1 \leq A_i \leq 500$$$).

The first line will contain a string that is either "YES" or "NO", that represents the existence of a correct partitioning.

• for 20 point it is guaranteed that $$$N \leq 20$$$
• for the other 80 points we have $$$N \leq 10^5$$$

5
1 2 1 2 3

YES

5
1 2 2 2 2

NO

For the first example, a valid partitioning is $$$[1,2], [2,1], [2,3]$$$ corresponding to the indices $$$[1,2], [2,3], [4,5]$$$.