Unique Element in Sorted List of Pairs

Given a sorted array of integers nums of size n. Every element appears twice expect for one. Return the element which appears only once.

Input Format

First Parameter - number n

Second Parameter - array of integers nums of size n

Output Format

Return the number.

Example 1

Input: 
    7
    1 1 3 3 4 5 5
Output:
    4

Example 2

Input:
    5
    1 2 2 3 3
Output:
    1

Constraints

• 0 < n < 10⁴
• 0 < arr[i] < 10⁵
• Expected Time Complexity: O(log n)
• Expected Space Complexity: O(1)