I. Inventing Communications
time limit per test
3 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

Iasmim, Pedro, and Emerson are preparing to present their own encryption method to the International Committee for Poor Communication (ICPC), the leading organization that studies poor communication methods that "work".

They have developed a unique and innovative method for transmitting messages. Since the idea is to create a bad communication method, they send an encrypted sequence of numbers. To decrypt and find the original message, one must find the lexicographically smallest non-empty subsequence of the vector $$$V$$$ such that its hash is strictly less than the hash of its complement. If a subsequence (of size $$$k$$$) consists of the positions $$$p_0, p_1, \ldots , p_{k-1}$$$, its complement is the subsequence composed of all the positions in the vector that are not any of these $$$k$$$ positions.

We say that a sequence $$$A$$$ is lexicographically smaller than a sequence $$$B$$$ if, at the first position where they diverge, the element of $$$A$$$ is smaller than the element of $$$B$$$. If the sequences are identical until the shorter one ends, the sequence of shorter length is considered the lexicographically smaller one.

The hash calculation used by the trio follows a polynomial hash structure. Given a subsequence (or its complement) composed of the numbers $$$x_0, x_1, \ldots , x_{k-1}$$$ in the order in which they appear in the vector $$$V$$$, the hash value $$$H$$$ is calculated using the following formula:

$$$$$$H = (x_0 \cdot P^N + x_1 \cdot P^{N-1} + \ldots + x_{k-1} \cdot P^{N-k+1}) \% M$$$$$$

Where:

  • $$$x_i$$$ is the value of the $$$i$$$-th element of the subsequence;
  • $$$P = 100019$$$ is the polynomial base;
  • $$$N$$$ is the total length of the vector $$$V$$$;
  • $$$M = 998244353$$$ is the modulus;
  • The index $$$i$$$ (from $$$0$$$ to $$$k-1$$$) represents the position of the number within the chosen subsequence.
  • By convention, the hash of an empty sequence ($$$k=0$$$) is defined as $$$0$$$.

You will be given the vector $$$V$$$ and must recover the subsequence that represents the message communicated by Iasmim, Pedro, and Emerson.

Input

The first line of the input contains a single integer $$$N$$$ $$$(1 \leq N \leq 10^6)$$$, the size of the vector $$$V$$$.

The second line of the input contains $$$N$$$ integers $$$V_i$$$: the elements of the vector $$$V$$$ $$$(1 \leq V_i \leq 10^5)$$$.

It is guaranteed that both $$$N$$$ and the vector $$$V$$$ are generated randomly for all hidden test cases.

Output

Print, on a single line, the lexicographically smallest non-empty subsequence $$$A$$$ of the vector $$$V$$$ such that $$$H(A) \lt H(A^c)$$$, where $$$A^c$$$ is the complement of $$$A$$$ in $$$V$$$. If no subsequence satisfies this condition, print $$$-1$$$ instead.

Note that the values of the subsequence must be printed, and not its positions. If two or more lexicographically equal subsequences occur in the vector in different positions such that they all satisfy the condition, you must print the values only once.

Examples
Input
5
60522 14575 36426 79445 48772
Output
14575
Input
5
90081 33447 90629 3497 47202
Output
3497
Note

It is guaranteed that the visible test cases are the only test cases generated without randomizing the size $$$N$$$ and the vector $$$V$$$.

In the first example test case, the lexicographically smallest subsequence of the vector is $$$[14575]$$$ and its hash is $$$405057492$$$. Its complement is the subsequence $$$[60522, 36426, 79445, 48772]$$$, which has a hash of $$$980706017$$$. As the lexicographically smallest subsequence already satisfies the condition, it should be printed.