Ignatius and the Princess IV

describe
“OK, you are not too bad, em… But you can never pass the next test.” feng5166 says.

“I will tell you an odd number N, and then N integers. There will be a special integer among them, you have to tell me which integer is the special one after I tell you all the integers.” feng5166 says.

“But what is the characteristic of the special integer?” Ignatius asks.

“The integer will appear at least (N+1)/2 times. If you can’t find the right integer, I will kill the Princess, and you will be my dinner, too. Hahahaha…..” feng5166 says.

Input
The input contains several test cases. Each test case contains two lines. The first line consists of an odd integer N(1<=N<=999999) which indicate the number of the integers feng5166 will tell our hero. The second line contains the N integers. The input is terminated by the end of file.

Output
For each test case, you have to output only one line which contains the special number you have found.

Sample Input

Sample Output

此題讓求奇數個數中出現次數超過總數一半的數，容易超時超內存，這里使用一種比較簡單的算法。首先要知道，在所有數中，去除兩個不同的數對結果沒有影響，利用這一點我們可以先記錄第一次輸入的數，如果和下一次輸入的數相同，計數器加一，否則減一（即去除兩個不同數）；當計數器為零時，這個數被全部去除，然后再記錄下一次輸入的數，重復上述操作。當輸入全部數之后，所留下的記錄的數就是答案。