410272: GYM103999 A String String

For Halloween, Mondialu went to each of his neighbors to ask for candies. In order to receive the maximum number of candies, he needs to be as scary as possible.

Mondialu has $$$n$$$ Halloween costumes $$$a_1, a_2, a_3, ... , a_n$$$. He needs to choose a subsequence (a sequence that can be derived from the array by deleting some or no elements without changing the order of the remaining elements) from the $$$n$$$ costumes (yes, Mondialu can wear multiple costumes, this is the level of scariness we are dealing with).

A subsequence is the scariest if it has the following properties:

• Has an even positive length.
• The first half of the subsequence is equal to the second half.
• It is the lexicographically largest subsequence.

An array $$$X$$$ is lexicographically larger than an array $$$Y$$$ if there exist an $$$i$$$ so that $$$x_1 = y_1, x_2 = y_2, ... , x_{i-1} = y_{i-1}$$$ and $$$x_i > y_i$$$ or if $$$Y$$$ is a prefix of $$$X$$$.

The first line of each test case contains a single integer $$$n$$$ $$$(1 \le n \le 10^5)$$$ — the length of the array.

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, a_3, ... , a_n$$$ $$$(1 \le a_i \le 10^9)$$$ — the elements of the array.

Output a single line, the elements of the scariest subsequence separated by spaces. If no such subsequence exists, print $$$-1$$$.

• $$$1 \le n \le 5$$$ for $$$20$$$ points
• $$$5 < n \le 100$$$ for $$$20$$$ points
• $$$100 < n \le 1000$$$ for $$$20$$$ points
• $$$1000 < n \le 100000$$$ for $$$40$$$ points

8
3 1 2 3 2 3 3 3

3 3 3 3 

3
1 2 3

-1

In the first example, the subsequence $$$3\ 3\ 3\ 3$$$ has an even positive length ($$$4$$$) and the first half $$$3\ 3$$$ is equal to the second half $$$3\ 3$$$. This is the lexicographically largest subsequence which respects the conditions.

In the second example, we cannot generate any subsequence which would respect the conditions, so the output is $$$-1$$$.