题目描述

有 $n$ 个同学参加狼人杀游戏，编号为 $1\sim n$，编号为 $i$ 的同学积分为 $a_i$。游戏共进行 $n-1$ 轮，每轮所有仍在游戏中的同学投票，票数最高的同学被淘汰，最后剩下的一位同学获胜。

对于每位仍在游戏中的同学 $i$：

1. 他优先投票给与自己积分差值 $|a_i-a_j|$ 最大的同学 $j$；
2. 如果有多位同学满足条件，则投票给积分较高的同学；
3. 如果积分仍相同，则投票给编号较大的同学。

每轮被淘汰的同学也按照“票数最多；票数相同时积分较高；积分仍相同时编号较大”的顺序确定。

请输出最后获胜的同学编号。

输入格式

本题采用文件读写。

• 读入文件名：werewolf.in
• 写出文件名：werewolf.out

第一行一个整数 $n$。

第二行 $n$ 个整数，第 $i$ 个数表示同学 $i$ 的积分。

输出格式

输出最后获胜的同学编号。

样例

5
1 2 3 4 5

1

数据范围与提示

• 对于 $20\%$ 的数据，$1\le n\le20,0\le a_i\le1000$。
• 对于 $50\%$ 的数据，$1\le n\le5000,0\le a_i\le10^9$。
• 对于全部数据，$1\le n\le10^6,-10^9\le a_i\le10^9$。