問題文

長さ $N$ の整数列 $x=(x_0,x_1,\\cdots,x_{N-1})$ があります（添字が $0$ から始まることに注意）． 最初，$x$ の要素はすべて $0$ です．

あなたは，以下の操作を好きな回数繰り返すことができます．

• 整数 $i,k$ ($0 \\leq i \\leq N-1$, $1 \\leq k \\leq N$) を選ぶ． その後，$i \\leq j \\leq i+k-1$ を満たすすべての $j$ について，$x_{j\\bmod N}$ の値を $1$ 増やす．

長さ $N$ の整数列 $A=(A_0,A_1,\\cdots,A_{N-1})$ が与えられます． $x$ を $A$ に一致させるために必要な最小の操作回数を求めてください．

制約

• $1 \\leq N \\leq 200000$
• $1 \\leq A_i \\leq 10^9$
• 入力される値はすべて整数

入力

入力は以下の形式で標準入力から与えられる．

$N$ $A_0$ $A_1$ $\\cdots$ $A_{N-1}$

出力

答えを出力せよ．

入力例 1

4
1 2 1 2

出力例 1

2

以下のように操作すればよいです．

• 最初，$x=(0,0,0,0)$ である．
• $i=1,k=3$ で操作を行う．$x=(0,1,1,1)$ となる．
• $i=3,k=3$ で操作を行う．$x=(1,2,1,2)$ となる．

入力例 2

5
3 1 4 1 5

出力例 2

7

入力例 3

1
1000000000

出力例 3

1000000000