#描述#
There are N sticks, and each stick has a corresponding length. One type of these sticks appears more than N/2 times, which is called P stick. Give you the all the sticks' length, could you find the P stick out?

#格式#
##输入格式##
The input file contains several test case, each test case starts with a number N ( 3&lt=N&lt=100,000), the number of the sticks, followed by a line with n integers len1, len2, len3…lenn(0&lt=bi&lt=2^31-1),which is the length of these sticks. The input is terminated by a test case with n = 0. It should not be processed.

##输出格式##
For each test case, output a line the P stick's length of the corresponding sequence.

#样例1#
##样例输入1##

4
3 4 3 3
7
4 5 4 2 4 4 2
0

##样例输出1##

3
4

#限制#
1000ms
32768KB

#提示#
It's a classical high offer interview problem, O(N) algorithm exits.

#来源#