Problem Description

总教头正在寻找他的最佳战斗伙伴。原始人王国里有 $n$ 个勇士，每个勇士的战斗力值记为 $a_i$。总教头决定通过一场淘汰赛来选择最终的战斗伙伴，比赛规则如下：

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

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

（ 题目保证所有勇士战力值不同 ）

Input Format

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

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

Output Format

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

5
2 3 6 1 10

4

68
77 66 7 52 95 51 29 94 56 98 59 19 76 5 32 64 54 81 57 60 53 93 26 3 47 33 49 27 46 87 43 1 17 10 11 71 61 58 44 80 16 35 74 72 99 30 69 4 31 82 83 100 21 40 68 34 14 23 41 38 91 12 89 55 37 28 84 13

23

Hint

数据范围

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