円環をなす $N$ 個( $N$ は偶数)のマスがあります。
あるマスから時計回りにマス $1$ , マス $2$ , $\ldots$ , マス $N$ と番号が付いています。
最初、マス $k$ には $A _ k$ 個の石が置いてあります。

マス $a$ にある石とマス $b$ にある石の距離は　$\min\lbrace \lvert a-b \rvert,N+a-b,N-a+b\rbrace$ であるとします。

ここから、石を選んで時計回りに $1$ マス動かす操作を繰り返します。
一連の操作を終えたとき、異なる $2$ つの石の組すべての距離の総和を得点として、得点があり得る最大値を取るようにします。

操作回数としてあり得る最小値を求めてください。

• $2 \leq N \leq 200{,}000$
• $N$ は偶数
• $0 \leq A _ i \leq 200{,}000$ ($1\leq i\leq N$)
• 入力はすべて整数

上記の制約に加えて以下の制約を満たすテストケースすべてに正解した場合、部分点として $50$ 点が与えられる。

• 石の総数は $4$ 以下である（つまり、 $\sum _ {i=1}^N A _ i\leq 4$）

答えとなる整数を $1$ 行に出力してください。