← 返回 amazon 的题目列表Single Element in a Sorted Array
类型：online_judge
Single Element in a Sorted Array
Given a non-empty integer array nums sorted in non-decreasing order, every element appears exactly twice except for one element that appears exactly once. Find and output that single element.
Your algorithm must run in O(log n) time and use O(1) extra space.
Input Format
First line: an integer n, the array length.
Second line: n integers in non-decreasing order.
Output Format
Print the element that occurs exactly once.
Constraints
1 <= n <= 100000
n is odd.
-10^9 <= nums[i] <= 10^9
Every value except one occurs exactly twice.
Example
Input:
9
1 1 2 3 3 4 4 8 8
Output:
2
Example
Input
1
7
Output
7