题目描述

我们有一个长度为$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$）。然后，对于$0 \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