n faraway Boboland, a king election is held every five years. This year is the time for another king election in Boboland. Each city in Boboland has nominated king candidates, numbered . These candidates have distinct political tendencies ( represents the political tendency of the -th candidate, where a larger number implies a more right-wing tendency, represents extreme left, and represents extreme right). Then, the following internal voting mechanism will be conducted among the candidates to decide the final king:

•  There will be rounds of voting, and exactly one candidate will be eliminated in each round until there is only one candidate left, who will become the final king.
• The voting rule for each round is as follows: each candidate can vote for any other candidate except for themselves. The candidate with the most votes will be eliminated. If there are multiple candidates with the same highest number of votes, the one among them with the rightmost tendency will be eliminated.

After observing all previous king elections in Boboland, you found that each candidate adheres to the principle of attacking opponents with different opinions and will execute the following strategy in each round of voting:

 Among all remaining candidates, vote for the candidate whose political tendency is most different from their own (i.e., the -th candidate, if they have not been eliminated, will vote for the -th candidate with the largest , who has not been eliminated). If there are multiple candidates with the largest , they will vote for the one among them with the rightmost tendency.


Now you want to know who will become the final king in this year's election in Boboland.

输入描述:

The first line contains a positive integer  , denoting the number of candidates.

The second line contains  distinct integers  , denoting the political inclination of each candidate.

输出描述:

Output an integer in a line, which represents the candidate's number who will eventually become the king.

4
5 1 8 10

1

4
10 1 9 6

3

4
3 7 5 1

4

备注:

To aid understanding, we provide a graphical illustration of the first sample test case. The following picture shows the first round of voting, with each candidate's preferred candidate indicated in the bubbles. At this point, candidates 2 and 4 are tied for the most number of votes, but candidate 4 has a more right-wing political leaning (), so candidate 4 is eliminated.



The following diagram shows the second round of voting, with candidate 2 receiving the most number of votes and candidate 4 being eliminated.



The following diagram shows the third round of voting, with candidates 1 and 3 tied for the most number votes, but candidate 3 having a more right-wing political leaning (), so candidate 3 is eliminated.


Therefore, candidate 1 is ultimately elected as the king.