Description

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?

Input

The input file contains several test case, each test case starts with a number N ( 3<=N<=100,000), the number of the sticks, followed by a line with n integers len1, len2, len3…lenn(0<=bi<=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.

Output

For each test case, output a line the P stick's length of the corresponding sequence.

Sample

Input

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

Output

3
4

Hint

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