#XSDCSPJ25043. 王老师的战斗伙伴
王老师的战斗伙伴
题目描述
在一个神秘的王国里,王老师正在寻找他的最佳战斗伙伴。王国里有 n 个勇士,每个勇士的战斗力值记为 。(保证战斗力值 互不相同)
王老师决定通过一场淘汰赛来选择最终的战斗伙伴,比赛规则如下:
- 竞技场将进行 轮投票淘汰,每轮淘汰一个勇士。
- 在每一轮中,第 个勇士会将自己的一票投给与自己战斗力值差距最大的勇士,即找到 j,使得 最。此轮得票最多的勇士将被淘汰。
- 如果有多个勇士得票相同,战斗力值较大的勇士优先被淘汰。
- 如果第 个勇士在本轮中有多个差距相同的候选目标,他会优先投票给战斗力值较大的勇士。
王老师想知道,在所有轮次结束后,剩下的勇士是谁。
输入格式
第一行包含一个整数 n,表示有 n 个勇士。
第二行包含 n 个整数,第 i 个整数 表示第 i 个勇士的战斗力值。
注:对于数据保证 互不相同
输出格式
输出一行一个整数,表示最终剩下的勇士的编号。
样例输入 1
5
2 3 6 1 10
样例输出 1
4
提示/说明
数据范围
对于 30% 的数据,满足
对于 50% 的数据,满足
对于 100% 的数据,满足