配点 : 500 点
問題文
在AtCoder Land,高桥君和青木君决定吃一块草莓蛋糕。
AtCoder Land的蛋糕是圆形的,N 通过一个半径方向的切口 N 被分成了若干扇形的份。
切口按顺时针顺序编号, 1给切口 2, \ldots给切口 N 编号后,从顺时针的切口 i (1 \leq i \leq N-1) 到切口 i+1 之间的部分称为Piece。 i 顺时针的切口 N 到切口 1 之间的部分称为Piece。 N 称为。
在Piece i (1 \leq i \leq N) 的上面 A_i 一个草莓放在上面。
高桥君和青木君将进行以下游戏。
- 首先,高桥君从 N 个切口中选择 1 个。选中的切口称为切口 i 。
- 接着,青木君从高桥君选择的切口以外的 N-1 个切口中选择 1 个。选中的切口称为切口 j 。
- 切口里选择。 i 高桥君按顺时针查看切口,直到切口 j ,并把范围内的所有碎片都拿走。
- 青木君拿走剩下的所有碎片。
- 高桥君拿到的碎片 1 每片草莓的数量平均值如果等于或大于青木君拿到的碎片 1 每片草莓的数量平均值,则高桥君获胜,否则青木君获胜。
当青木君选择最适合获胜的切口时,请求高桥君必须选择哪个切口才能获胜。如果没有这样的切口,请回答 -1 。如果存在多个,请回答编号最小的那一个。
制約
- 2 \leq N \leq 5 \times 10^{5}
- 0 \leq A_i \leq 5 \times 10^{5}
- 输入均为整数。
入力
输入将以以下格式从标准输入给出。
N A_1 A_2 \ldots A_N
出力
输出作为答案的切口编号。如果不存在答案切口,请输出 -1 。
入力例 1
3 3 8 5
出力例 1
2
当高桥君选择切口 1 时,青木君选择切口 2 ,高桥君将只能得到 1 ,青木君将得到 2,3 。高桥君所得到的片上草莓数量的平均值是 3,青木君所得到的片上草莓数量的平均值是 6.5 。因此青木君获胜。
当高桥君选择切口 2 时选择时,无论青木君选择哪个切入点,高桥君都会获胜。因此,答案是 2 。
入力例 2
15 4096 64 512 1 256 16384 8 1024 2048 2 128 32 4 16 8192
出力例 2
15