### 問題文

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

• 整数 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 増やす．

### 制約

• 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}


### 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