Description

There are $n$ positive integers $a_i$. He asks redbag to find the mode. He also specifically states that this mode occurs more than half of the $n$ elements.

Input Format

The first line contains an integer $n$, the number of values.
The second line contains $n$ positive integers $a_i$.

Output Format

Output one line with a single integer, the mode.

5
2 3 3 3 3

3

Hint

Constraints
For $100\%$ of the testdata, $1 \le n \le 2 \times 10^6$, $a_i \in [1, 2^{31})$.

Some may want to take the easy way out, but the memory is not enough.

//kkksc03 whispers: Just output any number; you have a 1/2 chance. But this is "Le Duo Sai", whether it is worth it is up to you. So you had better think about the proper solution.

Translated by ChatGPT 5