Single Number

Given an array of integers, every element appears twice except for one unique element that appears only once. Your task is to find and output this single number.

You are guaranteed that exactly one element appears once, and all other elements appear exactly twice. An efficient solution is expected, preferably with a linear time complexity and constant extra space.

Hint: The bitwise XOR operation has properties that can be useful in solving this problem. In particular, for any integer \(a\), \(a \oplus a = 0\) and \(a \oplus 0 = a\).

inputFormat

The first line of the input contains a single integer \(n\) (\(1 \le n \le 10^5\)) representing the number of elements in the array.

The second line contains \(n\) space-separated integers. It is guaranteed that all elements appear exactly twice except for one element which appears only once.

outputFormat

Output a single line containing the unique number that appears only once.

## sample

5
4 1 2 1 2

4

</p>