题目描述

在一个神秘的王国里，王老师正在寻找他的最佳战斗伙伴。王国里有 n 个勇士，每个勇士的战斗力值记为 $a_i​$ 。（保证战斗力值 $a_i$​ 互不相同）

王老师决定通过一场淘汰赛来选择最终的战斗伙伴，比赛规则如下：

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

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

输入格式

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

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

注：对于数据保证 $a_i​$ 互不相同

输出格式

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

样例输入 1

5
2 3 6 1 10

样例输出 1

4

提示/说明

数据范围

对于 30% 的数据，满足 $n≤20，0≤a_i​ ≤1000$

对于 50% 的数据，满足 $n≤5000，0≤a_i ≤10^9$

对于 100% 的数据，满足 $n≤10^6 ，−10^9 ≤a_i ≤10^9$