A warehouse scans every item's SKU code twice, once inbound and once outbound, so its sorted scan log lists each SKU exactly twice — except a single lost item whose SKU appears only once. The log is sorted in non-decreasing order, so the two copies of each paired SKU are adjacent.
Print the SKU value that appears only once. Solve it in logarithmic time using the sorted structure.
Input format
Line 1: an odd integer n, the number of scans.
Line 2: n space-separated integers in non-decreasing order; every value appears exactly twice except one value that appears once.
Output format
A single integer: the value that appears exactly once.
Constraints
- n is odd, 1 <= n <= 199999
- 1 <= each value <= 1000000000
- The list is sorted non-decreasingly; exactly one value appears once, all others exactly twice.