配点 : $500$ 点

問題文

長さ $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}$

出力

答えを出力せよ．

4
1 2 1 2

2

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

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

5
3 1 4 1 5

7

1
1000000000

1000000000