First repeated ticket ID

Problem

At a college fest, volunteers scan entry tickets one by one. Each ticket has an ID. A fake ticket is a copy of an ID that was already scanned.

Going through the scans in order, find the first scan whose ID was already scanned earlier, and print that ID. If no ID is ever repeated, print -1.

Input: The first line has one integer n. The second line has n integers: the ticket IDs in the order they were scanned.
Output: One integer: the first ID that is scanned for the second time, or -1.
Constraints: 1 ≤ n ≤ 10^5
1 ≤ ID ≤ 10^9

Example 1

Input

6
5 3 8 3 5 1

Output

ID 5 was scanned first, but its copy comes at scan 5. The copy of 3 comes earlier, at scan 4.

Example 2

Input

4
10 20 30 40

Output

-1

Every ID is different.

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

Hint 1

For each scan you only need to know one thing: has this ID been seen before?

Hint 2

Comparing with every earlier scan works but costs O(n²) in total.

Hint 3

Keep the IDs seen so far in a HashSet. The first ID that is already in the set is the answer.

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