Find the First Duplicate Integer

Given an array of integers, your task is to find the first duplicate element when traversing the array from left to right. If there is no duplicate, output -1.

More formally, given an array $A = [a_1, a_2, \ldots, a_n]$, you need to find the smallest index $i$ such that there exists a $j$ with $j < i$ and $a_j = a_i$. If no such index exists, print -1.

inputFormat

The first line of input contains an integer $n$ — the number of elements in the array. The second line contains $n$ space-separated integers, representing the array.

outputFormat

Output a single integer: the first duplicate encountered while traversing the array from left to right. If there is no duplicate, output -1.## sample

7
1 2 3 4 2 5 6

2