该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

徐老师最近很喜欢玩狼人杀，于是他决定在 OJ 里办一个信奥狼人杀

一共有 $n$ 个同学参加游戏，编号为 $1 \sim n$，编号为 $i$ 的同学在 OJ 上的积分为 $a_i$

游戏一共进行 $n-1$ 轮，每轮所有人会进行投票，票数最高的同学会被淘汰，最后剩下一位同学获胜

徐老师在游戏过程中发现，原来每个同学的投票都是有规律的！

1. 对于每位同学而言，第 $i$ 位同学都会优先投票给和自己积分差值最大的同学 $j$，形式化的说，就是会选择一位同学 $j$ 使得 $|a_i - a_j|$ 最大
2. 对于第 $i$ 位同学，如果有多位同学 $j$ 使得 $|a_i - a_j|$ 最大，那么他会优先投票给 $a_j$ 最大的同学
3. 如果在某一轮中有多位同学的得票数都是最高，那么这一轮会优先淘汰积分最高的同学

现在徐老师想知道，对于一次游戏，他已经知道所有同学的积分了，最后会获胜的人是谁？

输入格式

输入一行，包含一个整数 $n$ 表示有 $n$ 个同学

输入第二行包含 $n$ 个整数，第 $i$ 个数字表示编号为 $i$ 的同学的积分

输出格式

输出一个整数，表示最后获胜同学的编号

数据范围

对于 $20\%$ 的数据，保证 $1 \leq n \leq 20, 0 \leq a_i \leq 1000$

对于 $50\%$ 的数据，保证 $1 \leq n \leq 5000, 0 \leq a_i \leq 10^9$

对于 $100\%$ 的数据，保证 $1 \leq n \leq 10^6, -10^9 \leq a_i \leq 10^9$

特别的，保证所有同学的积分各不相同

样例输入

5
1 2 3 4 5

样例输出

1