You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

在一个神秘的王国里，有一位伟大的勇者正在寻找他的最佳战斗伙伴。王国里有 $n$ 个勇士，每个勇士的战斗力值记为 $a_i$。勇者决定通过一场淘汰赛来选择最终的战斗伙伴，比赛规则如下：

• 竞技场将进行 $n-1$ 轮投票淘汰，每轮淘汰一个勇士。
• 在每一轮中，第 $i$ 个勇士会将自己的一票投给与自己战斗力值差距最大的勇士，即找到 $j$，使得 $|a_i - a_j|$ 最大。此轮得票最多的勇士将被淘汰。
• 如果有多个勇士得票相同，战斗力值较大的勇士优先被淘汰。
• 如果第 $i$ 个勇士在本轮中有多个差距相同的候选目标，他会优先投票给战斗力值较大的勇士。

勇者想知道，在所有轮次结束后，剩下的勇士是谁。

输入格式

第一行包含一个整数 $n$，表示有 $n$ 个勇士。

第二行包含 $n$ 个整数，第 $i$ 个整数 $a_i$ 表示第 $i$ 个勇士的战斗力值。

输出格式

输出一行一个整数，表示最终剩下的勇士的编号。

5
2 3 6 1 10

4

数据范围

• 对于 $30\%$ 的数据，满足 $n \leq 20$，$0 \leq a_i \leq 1000$
• 对于 $50\%$ 的数据，满足 $n \leq 5000$，$0 \leq a_i \leq 10^9$
• 对于 $100\%$ 的数据，满足 $n \leq 10^6$，$-10^9 \leq a_i \leq 10^9$

保证所有$a_i$互不相同