First Repeated Value in the Range 0..1000

Source: Phước Hưng OJ

Version: Phuoc Hung OJ Extended

Problem

Given $a_0,a_1,\ldots,a_{n-1}$ with $0\le a_i\le1000$, scan left to right. Let

if such an index exists. Print $a_p$, the first value encountered for the second time. If no value repeats, print -1.

Input

The first line contains $n$. The second line contains $n$ integers in $[0,1000]$.

Output

Print the first repeated value, or -1 if there is none.

Subtask

Subtask 1 (20 points): $1\le n\le 10$, $0\le a_i\le 1000$.

Subtask 2 (30 points): $1\le n\le 5000$, $0\le a_i\le 1000$.

Subtask 3 (50 points): $1\le n\le 2\cdot 10^5$, $0\le a_i\le 1000$.

Example

Input

7
4 1 7 4 1 9 7

Output

4

Explanation

The output follows directly from the mathematical definition above.