题目描述

長さ $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$ に一致させるために必要な最小の操作回数を求めてください．

输入格式

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

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

输出格式

答えを出力せよ．

题目大意

你有一个长度为 $n$ 的序列 $x$，其中元素由 $0$ 到 $n-1$编号。序列各元素初始全为 $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} \leftarrow x_{j \bmod n} + 1$。

（通俗地讲就是将序列首尾相接拼成一个环，每次选取环上的一段，将其上元素的值全部加 $1$。）

现给定另一个序列 $A$，求出由 $x$ 变换为 $A$ 所需的最小操作数。

4
1 2 1 2

2

5
3 1 4 1 5

7

1
1000000000

1000000000

提示

制約

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

Sample Explanation 1

以下のように操作すればよいです． - 最初，$x=(0,0,0,0)$ である． - $i=1,k=3$ で操作を行う．$x=(0,1,1,1)$ となる． - $i=3,k=3$ で操作を行う．$x=(1,2,1,2)$ となる．