問題文

AtCoder Land で高橋君と青木君はイチゴの乗ったケーキを食べることになりました。

AtCoder Landのケーキは円形で、N 個の半径方向の切れ込みによって N 個の扇形ピースに区切られています。

切れ込みを時計回りの順に切れ込み 1, 切れ込み 2, \ldots, 切れ込み N と番号をふったとき、時計回りに切れ込み i (1 \leq i \leq N-1) から切れ込み i+1 までの間の部分をピース i と呼びます。また、時計回りに切れ込み N から切れ込み 1 までの間の部分をピース N と呼びます。

ピース 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}
• 入力は全て整数

入力例 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