Find the Duplicate Number

You are given a list of integers. Your task is to find the first element that appears more than once and print it. If no such element exists, print -1.

The solution should operate in $O(n)$ time and use $O(n)$ space.

For example:

• For the input [1, 2, 3, 4, 5], the output should be -1 because there is no duplicate.
• For the input [1, 2, 3, 4, 2], the output should be 2 as 2 appears more than once.
• For the input [3, 3, 3, 3, 3, 3], the output should be 3.

inputFormat

The input is provided via stdin and consists of two lines:

• The first line contains an integer n ($n\ge0$), the number of elements in the list.
• The second line contains n space-separated integers representing the list.

outputFormat

Output a single integer to stdout: the first duplicate number found. If there is no duplicate, output -1.

5
1 2 3 4 5

-1