Single Element in a Sorted Array

You are provided with a sorted (non‑decreasing) integer sequence arr that has an odd number of elements. Within this sequence, every integer occurs exactly two times, except for one value that appears only once. Your task is to identify and return this unique number.

Your solution must run in O(log n) time and must use at most O(1) additional memory beyond the input.

Input

• Implement singleElement(arr), where arr is a list of n integers (n is the total count of elements), sorted in non‑decreasing order.

Output

• Return the single integer that occurs exactly once.

Example 1:

Input:
7
11 11 22 22 33 44 44

Output:
33

Explanation: The pairs are 11, 22 and 44. The number 33 appears exactly once.

arr = [11, 11, 22, 22, 33, 44, 44]

33

Example 2:

Input:
5
5 5 6 6 7

Output:
7

Example 3:

Input:
1
99

Output:
99

Constraints:

• 1 <= n <= 200 001 and n is guaranteed to be odd.
• -2 147 483 648 <= arr[i] <= 2 147 483 647
• Every value appears exactly twice, except for a single value that appears exactly once.
• The input array is sorted in non‑decreasing order.
• Your algorithm must achieve O(log n) time complexity and O(1) extra space complexity.

Example (as reported)

Input:
1
7

Output:
7