Single Number

Given a non-empty array of integers in which every element appears twice except for one, your task is to find that single number. The solution must run in linear time \(O(n)\) and use constant extra space \(O(1)\). This problem is best solved using the bitwise XOR operator, which has the property that \(a \oplus a = 0\) and \(a \oplus 0 = a\). Therefore, by XORing all numbers together, the duplicates cancel out, leaving only the unique number.

Example:

Input: 3
       2 2 1
Output: 1
Input: 5
4 1 2 1 2
Output: 4

</p>

inputFormat

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

outputFormat

Output a single integer, which is the number that appears only once in the array.

## sample

3
2 2 1

1

</p>