Description

有n个数字，其中有一个数字的出现次数超过总个数的一半，这个数称之为英雄数。
例如，n=12，整数序列5，5，5，5，5，5，1，2，3，4，5，6，其中的英雄数为5。

对于给定的n个整数组成的序列，请使用数据结构堆栈，设计出一个时间复杂度为O(n)算法，计算出序列中的英雄数。

Input

由键盘提供输入数据。文件的第1行有1个正整数n<=1000000，表示整数序列有n个整数。第2行是整数序列，整数大小都在32位有符号整型内，数字之间以一个空格隔开。
输入数据保证必然存在一个数字，其出现次数超过总个数的一半。

Output

程序运行结束时，将指定序列的英雄数输出到屏幕上。

Sample Input


12
5 5 5 5 5 5 1 2 3 4 5 6

Sample Output


5

Source