/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 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}
出力
答えを出力せよ．
入力例 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
Score : 500 points
Problem Statement
We have an integer sequence of length N: x=(x_0,x_1,\cdots,x_{N-1}) (note that its index is 0-based). Initially, all elements of x are 0.
You can repeat the following operation any number of times.
- Choose integers i,k (0 \leq i \leq N-1, 1 \leq k \leq N). Then, for every j such that i \leq j \leq i+k-1, increase the value of x_{j\bmod N} by 1.
You are given an integer sequence of length N: A=(A_0,A_1,\cdots,A_{N-1}). Find the minimum number of operations needed to make x equal A.
Constraints
- 1 \leq N \leq 200000
- 1 \leq A_i \leq 10^9
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N
A_0 A_1 \cdots A_{N-1}
Output
Print the answer.
Sample Input 1
4 1 2 1 2
Sample Output 1
2
We should do the following.
- Initially, we have x=(0,0,0,0).
- Do the operation with i=1,k=3, making x=(0,1,1,1).
- Do the operation with i=3,k=3, making x=(1,2,1,2).
Sample Input 2
5 3 1 4 1 5
Sample Output 2
7
Sample Input 3
1 1000000000
Sample Output 3
1000000000