Find the First Duplicate

You are given a list of integers. Your task is to find the first duplicate element in the list. In other words, when traversing the list from left to right, you need to find the first element that has appeared before.

If there is no duplicate in the list, output -1.

Formally, given a sequence \(a_1, a_2, \ldots, a_n\), find the smallest index \(i\) such that there exists some \(j < i\) with \(a_i = a_j\). If no such \(i\) exists, print \(-1\).

inputFormat

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

outputFormat

Output a single integer which is the first duplicate element found in the list. If no duplicate exists, output -1.## sample

5
1 2 3 4 5

-1