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 n 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