Circular Addition

时间限制：2s
空间限制：1024MB

题目描述

有一个长度为 $N$ 的整数序列 $x=(x_0,x_1,\ldots,x_{N-1})$。初始时，所有元素均为 $0$。

你可以进行任意次如下操作：选择整数 $i,k$，其中 $0\le i<N$、$1\le k\le N$；对于所有满足 $i\le j\le i+k-1$ 的 $j$，令 $x_{j\bmod N}$ 增加 $1$。

给定目标序列 $A=(A_0,A_1,\ldots,A_{N-1})$，求把 $x$ 变成 $A$ 所需的最少操作次数。

输入格式

第一行输入一个整数 $N$。

第二行输入 $N$ 个整数 $A_0,A_1,\ldots,A_{N-1}$。

输出格式

输出最少操作次数。

样例输入 1

4
1 2 1 2

样例输出 1

2

样例输入 2

5
3 1 4 1 5

样例输出 2

7

样例输入 3

1
1000000000

样例输出 3

1000000000

数据范围

对于所有数据，$1\le N\le 2\times 10^5$，$1\le A_i\le 10^9$。