Single Number

You are given an array of integers where every element appears exactly twice except for one element which appears only once. Your task is to find that single number.

The solution can be achieved using the bitwise XOR operation. Recall that the XOR operation has the following properties:

• Commutative: \(a \oplus b = b \oplus a\)
• Associative: \(a \oplus (b \oplus c) = (a \oplus b) \oplus c\)
• Identity: \(a \oplus 0 = a\)
• Self-inverse: \(a \oplus a = 0\)

Using these properties, if you XOR all the elements of the array, the pairs will cancel each other out (yielding 0) and the single number will be the result.

inputFormat

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

It is guaranteed that \(n \geq 1\) and that exactly one element appears once while all others appear exactly twice.

outputFormat

Output a single integer --- the number that appears only once in the array.

## sample

5
1 2 3 2 1

3

</p>