Find the Single Element in a Sorted Array

You are given a sorted array of integers in which every element appears exactly twice except for one element which appears only once. Your task is to find and output that single element.

The expected time complexity is \(O(\log n)\), suggesting the use of a binary search approach.

Example:

Input: 5
       1 1 2 2 3
Output: 3

Note: The input is read from stdin and the output should be printed to stdout.

inputFormat

The first line of input contains a single integer \(n\), the number of elements in the array. The second line contains \(n\) space-separated integers representing the sorted array.

outputFormat

Output the single element which occurs only once in the array.

5
1 1 2 2 3

3