The Single Element in a Sorted List

nums is sorted. Every value appears exactly twice, except for one value that appears once. Return that value.

Examples

Example 1

Input:

single_non_duplicate([1, 1, 2, 3, 3, 4, 4, 8, 8])

Output:

2

Example 2

Input:

single_non_duplicate([3, 3, 7, 7, 10, 11, 11])

Output:

10

Constraints

• 1 <= len(nums) <= 2 * 10**5 + 1, and the length is odd
• nums is sorted in non-decreasing order.
• 0 <= nums[i] <= 10**9
• The big tests count how many values your code reads from the list (the limit is stated in the failure message). Reading every value, or using in, .index, .count, min or sorted on the whole list, fails them.