题目描述

有一个长度为 $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$ $A_2$ $\cdots$ $A_{N-1}$

输出格式

请输出答案。

样例 1

输入

4
1 2 1 2

输出

2

样例 2

输入

5
3 1 4 1 5

输出

7

样例 3

输入

1
1000000000

输出

1000000000

说明/提示

限制条件

• $1 \leq N \leq 200000$
• $1 \leq A_i \leq 10^9$
• 输入的所有值均为整数

样例解释 1

可以按如下方式进行操作：

• 最初，$x=(0,0,0,0)$。
• 选择 $i=1, k=3$ 进行操作，此时 $x=(0,1,1,1)$。
• 选择 $i=3, k=3$ 进行操作，此时 $x=(1,2,1,2)$。

由 ChatGPT 4.1 翻译