Single Number

Problem statement

A device inventory log contains two scans for every registered device except one device that was scanned only once. The audit must recover that unpaired identifier without sorting or allocating a lookup table. Your task Find the single value appearing once when every other value appears exactly twice. Use O(n) time and O(1) auxiliary space. Important details Equal identifiers need not be adjacent, and identifiers may be negative. The input guarantee applies to exactly one value. Bitwise XOR cancels paired occurrences while preserving the unpaired identifier; ordinary addition does not have this property. Worked example For [4, 1, 4, 7, 1], the two 4s and two 1s are paired. Only 7 remains, so the answer is 7.

Input format

The first line contains n. The next line contains n space-separated integers; for n = 0 this line may be empty.

Output format

Print the unpaired value.

Constraints

1 <= n <= 30000; -30000 <= values <= 30000; exactly one value occurs once and all others twice.

Sample input

5
4 1 4 7 1

Sample output

7