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

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