← 返回题目列表

AtCoder · codequeen2024_final_f

I. 分蛋糕

中文机器翻译题面 查看原题

配点 : 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