C2 - Shorts

問題

あつおくんは、Pixiw Shorts という動画配信サービスを利用しています。

Pixiw Shorts には、現在 $N$ 個の動画がアップロードされています。
アクセスするとまずどれかの動画が一様ランダムに表示されています。

動画 $i$ を見ているとき上にスクロールすると動画 $i-1$ が、下にスクロールすると動画 $i+1$ が表示されます。
もちろん、スクロールしなければ動画がもう一度流れます。
ただし、動画 $0$ は動画 $N$ 、動画 $N+1$ は動画 $1$ をさします。

あつおくんは動画 $i$ を少なくとも $A_i$ 回視聴しました。
あつおくんのスクロール回数として考えられる最も小さな値を出力してください。

制約

• $1\leq N\leq 2\times 10^5$
• $0\leq A_i\leq 10^9$

入力例1

5
1000000000 0 0 0 1
Copy

出力例1

1
Copy

あつおくんが動画 1 を $1000000000$ 回みたあと、一度だけ上にスクロールした場合最小となります。

入力例2

4
0 0 0 0
Copy

出力例2

0
Copy

あつおくんが動画 2 を $10^{10^{100}}$ 回みたあと、そのまま閉じた場合にこの値を達成できます。

入力例3

6
1 1 1 1 1 1
Copy

出力例3

5
Copy