Find the Single Number

You are given an array of integers in which every element appears exactly twice except for one element that appears only once. Your task is to find and output this unique element.

Note that you are not allowed to use extra memory. A hint: You can make use of the properties of the XOR operator, where \(a \oplus a = 0\) and \(a \oplus 0 = a\) to solve the problem in linear time and constant space.

Example:

Input:
3
2 2 1
Output:
1

inputFormat

The input consists of two lines. The first line contains an integer (n), the number of elements in the array. The second line contains (n) space-separated integers.

outputFormat

Output a single integer which is the unique number that appears only once in the array.## sample

3
2 2 1

1