2052：站斗伙伴
文件提交：无需freopen
内存限制：128 MB
时间限制：1.000 S
评测方式：普通裁判
命题人：
提交：2
解决：2
题目描述
在一个神秘的王国里，王老师正在寻找他的最佳战斗伙伴。王国里有 $n$ 个勇士，每个勇士的战斗力值记为 $a_i$。（保证战斗力值 $a_i$ 互不相同）
王老师决定通过一场淘汰赛来选择最终的战斗伙伴，比赛规则如下：
王老师决定通过一场淘汰赛来选择最终的战斗伙伴，比赛规则如下：
- 竞技场将进行 $n−1$ 轮投票淘汰，每轮淘汰一个勇士。
- 在每一轮中，第 $i$ 个勇士会将自己的一票投给与自己战斗力值差距最大的勇士，即找到 $j$，使得 $|a_i-a_j|$ 最大。此轮得票最多的勇士将被淘汰。
- 如果有多个勇士得票相同，战斗力值较大的勇士优先被淘汰。
- 如果第 $i$ 个勇士在本轮中有多个差距相同的候选目标，他会优先投票给战斗力值较大的勇士。
输入
第一行包含一个整数 $n$，表示有 $n$ 个勇士。
第二行包含 $n$ 个整数，第 $i$ 个整数 $a_i$ 表示第 $i$ 个勇士的战斗力值。
注：对于数据保证 $a_i$ 互不相同
$1\le n\le 10^6, -10^9\le a_i\le 10^9$
输出
输出一行一个整数，表示最终剩下的勇士的编号。
样例输入-1 复制
5
2 3 6 1 10样例输出-1 复制
4