P2397 yyy Loves Math VI (mode) / Moore Voting

Since last time redbag used addition to give yyy a hard time, yyy was furious. He struck back by giving redbag a problem, but to his surprise he could not solve it himself, so he turned to you.

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.

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

Output one line with a single integer, the mode.

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