题目描述

给定一个长度为$n$的序列：$A_1,A_2......A_n$，求其中出现次数超过一半的数。（保证给出的序列有且仅有1个整数出现次数超过一半）

输入

第一行输入一个整数$n$，表示序列$A$的长度。 第二行输入$n$个数，分别是$A_1,A_2......A_n$。

输出

一个整数，即在序列中出现次数超过一半的数。

样例数据

5
1 1 2 4 1

1

数据范围

$0<n\le10^6$

$-2^{31}\le A_i<2^{31}$