#XSDCSPJ25043. 王老师的战斗伙伴

王老师的战斗伙伴

题目描述

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

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

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

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

输入格式

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

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

注:对于数据保证 aia_i​ 互不相同

输出格式

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

样例输入 1

5
2 3 6 1 10

样例输出 1

4

提示/说明

数据范围

对于 30% 的数据,满足 n200ai1000n≤20,0≤a_i​ ≤1000

对于 50% 的数据,满足 n50000ai109n≤5000,0≤a_i ≤10^9

对于 100% 的数据,满足 n106109ai109n≤10^6 ,−10^9 ≤a_i ≤10^9