MAJORITY - Finding Majority

no tags 

Given an array A of N integers in which the most frequent item appear more than N / 2 times, determine this value.

Input

The first line contain N (1 <= N <= 3000000) then N 32-bit integers per line.

Output

The output consists of one number: the most frequent item on A.

Example

Input:
5
2
3
2
2
4 Output: 2

hide comments
sdfghjgr: 2017-11-04 12:04:51

Time limits are not strict enough. My nlogn solution was accepted :(

:): 2012-07-20 14:44:37

hey its a tutorial!!!

eddy: 2012-07-20 03:12:33

must be moved to the tutorial!

Francky: 2012-07-20 03:12:33

There's a typo in first line with 'N' and 'n'.
This problem belongs to tutorial for sure.

Sidharth Gupta: 2012-07-20 03:12:33

tutorial!

devu: 2012-07-20 03:12:33

move it to tutorials


Added by:Frank Rafael Arteaga
Date:2012-07-19
Time limit:0.100s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Classic problem