The Unpaired Value

In the sorted list nums every value appears exactly twice, except for one value that appears exactly once. Return that value.

Examples

Input:  nums = [1, 1, 2, 3, 3, 4, 4]
Output: 2

Input:  nums = [1, 1, 2, 2, 3]
Output: 3

Input:  nums = [0, 1, 1]
Output: 0

Constraints

• len(nums) is odd and 1 <= len(nums) <= 10**6
• O(log n) time is required; a full scan (or a Counter) is too slow on the largest tests.

Goals

• Use index parity to tell which side of the array contains the odd one out
• Keep the search space aligned to pairs