Find the Duplicate Number

You are given an integer n and an array of n integers. Each integer in the array is in the range \( [1, n-1] \). It is guaranteed that exactly one number appears at least twice in the array, while all other numbers appear exactly once. Your task is to identify and print the duplicate number.

Note: The array is unsorted and may contain the duplicate number anywhere in the list.

inputFormat

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

• The first line contains a single integer \( n \) representing the number of elements in the array.
• The second line contains \( n \) space-separated integers representing the array elements.

outputFormat

Output the duplicate number to stdout.

## sample

5
4 3 2 1 4

4

</p>