First repeated id

Problem

Scan n ids from left to right. Print the first id that has already appeared earlier in the list. Print -1 when every id is new.

Example

Input

6
4 8 15 8 4 16

Output

The second 8 comes before the second 4.

Try the problem first. Open one hint at a time.

Hint 1

Remember the ids you have seen in a set.

Hint 2

Stop at the first id that is already in the set.

Write your Python code, run it on the examples and submit it to hidden tests.