Find the Single Number

You are given a list of integers in which every integer appears exactly twice except for one integer which appears only once. Your task is to find and print that unique integer. If the list is empty, print 0.

The solution can be succinctly derived using the bitwise XOR operator, as for any integer a it holds that a \oplus a = 0 and a \oplus 0 = a. Thus, by XORing all numbers together, the duplicate numbers cancel out leaving the unique number.

inputFormat

The input is read from stdin and consists of two lines:

• The first line contains an integer n representing the number of elements in the list.
• The second line contains n space-separated integers. If n is 0, then there is no second line and the list is considered empty.

outputFormat

Output to stdout a single integer, which is the element that appears only once in the list. If the input list is empty, output 0.

5
4 1 2 1 2

4