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

- 竞技场将进行 n-1 轮投票淘汰，每轮淘汰一个勇士。

- 在每一轮中，第 i 个勇士会将自己的一票投给与自己战斗力值差距最大的勇士，即找到 j，使得 |a_i - a_j| 最大。此轮得票最多的勇士将被淘汰。

- 如果有多个勇士得票相同，战斗力值较大的勇士优先被淘汰。

- 如果第 i 个勇士在本轮中有多个差距相同的候选目标，他会优先投票给战斗力值较大的勇士。

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

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

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

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

数据范围

- 对于 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