Demux Problems Submissions Users Contests Log in Sign up


Always Single


Submit solution

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


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

    the example above is not a sorted array


    • 0
      manojbvs  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