9030: Election of the King

内存限制:128 MB 时间限制:1 S
题面:传统 评测方式:文本比较 上传者:
提交:10 通过:8

题目描述

In 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 nnn king candidates, numbered 1,2,…,n . These  candidates have distinct political tendencies a1,a2,…,an(1< ai < 109) represents the political tendency of the i-th candidate, where a largenumber implies a more right-wing tendency, 1 represents extreme left, and 109 reprsents extreme right). Then, the following internal voting mechanism will be conducted among the
candidates to decide the final king:
There will be n - 1 rounds of voting, and exactly one candidate will be elimin:ited in each round until there is only one candidate left, who will become the final kingThe voting rule for each round is as follows: each candidate can vote for any oner candidate except for themselves, The candidate with the most votes will be elimirted, f there are mu tiple candidates with the same highest number of votes, the one among them withthe rightmost tendency will be eliminated.
After observing all previous king elections in Boboland, you found that each candidte adheres to the principle of attacking opponents with different opinions and will exeute the following strategy in each round of voting:
Among all remaining candidates, vote for the candidate whose political tendency ismost different from their own (i.e., the i-th candidate, if they have not been eliminatecwill vote for the -th candidate with the largest aj - ai , who has not been eliminated). lf there aremultiple candidates with the largest aj - ai , 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 Boboand

输入格式


The first line contains a positive integer n (1≤n≤106), denoting the number of candidates.
The second line contains n distinct integers a1,a2,…,an (1≤ai≤109), 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