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, \dots , 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, \t{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, \dots , x_{i-1} = y_{i-1}$ and $x_i > y_i$ or if $Y$ is a prefix of $X$.

Input data

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, \dots , a_n$, $1 \le a_i \le 10^9$ - the elements of the array.

Output data

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

Constraints and clarifications

• $1 \le n \le 5$ for $20$ points;
• $5 < n \le 100$ for $20$ points;
• $100 < n \le 1 \ 000$ for $20$ points;
• $1 \ 000 < n \le 100 \ 000$ for $40$ points.

Example 1

stdin

8
3 1 2 3 2 3 3 3

stdout

3 3 3 3

Explanation

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.

Example 2

stdin

3
1 2 3

stdout

-1

Explanation

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