## Always Single

Points: 100
Time limit: 2.0s
Memory limit: 128M

Author:
Problem type
Allowed languages
C, C++, Java, Python

You are given a sorted array $$A$$ of $$N$$ integers. There is special property about $$A$$, every element in $$A$$ appears exactly twice, except for one element which appears exactly once.

Your task is to find that single element that appears that exactly once.

Example

$$N = 5$$, $$A = [0,0,1,1,2]$$

except $$2$$ every element appears twice, hence answer should be $$2$$.

#### Input

First line contains single integer: $$N$$.

Second line contains $$N$$ integers, where $$i^{th}$$ integer is $$A[i]$$.

#### Output

Print the single element that appears that exactly once in given array.

#### Constraints

$$1$$ $$\leq$$ $$N$$ $$\leq$$ $$10^5$$

$$0$$ $$\leq$$ $$A[i]$$ $$\leq$$ $$10^9$$

##### Example

Input

5
2 2 4 4 1

Output

1

Note

You can use this template to submit the solution.

## Comments

• commented on May 24, 2021, 11:54 a.m.

the example above is not a sorted array

• commented on June 14, 2021, 11:35 a.m. edited

I think they wanted to say duplicates occur together in the array. Only then binary search can be applied