Find the First Duplicate

You are given an array of integers. Your task is to find and print the first duplicate number such that its second occurrence has the minimal index. If there is no duplicate in the array, output -1.

For example, if you are given the array [2, 1, 3, 5, 3, 2], the first duplicate is 3 because the second occurrence of 3 (at index 4) appears before the second occurrence of 2. The problem can be formally defined as follows:

Given an array \(A = [a_1, a_2, \dots, a_n]\), find the first \(a_i\) (as you traverse the array) for which there exists a \(j < i\) such that \(a_j = a_i\). If no such element exists, return \(-1\).

inputFormat

The input is read from standard input. The first line contains an integer \(n\) representing the number of elements in the array. The second line contains \(n\) space-separated integers.

outputFormat

Output the first duplicate number found. If there is no duplicate, print -1. The output is written to standard output.

6
2 1 3 5 3 2

3