题面描述

小 Z 有一个长度为 $n$ 的数组 $A=\{a_1,a_2,\cdots,a_n\}$，他可以进行任意次如下操作：

1. 加法操作：对于所有 $i \in [n-l+1,n]$ 的 $a_i$，执行 $a_i+(i+l-n)$ 的操作，其中 $l$ 是小 Z 选择的执行参数，只需要满足 $1\le l \le n$ 的任意整数。换句话说，小 Z 可以选择一个整数 $l\in [1,n]$，然后执行 $a_n+l, a_{n-1}+l-1,a_{n-2}+l-2,\cdots, a_{n-l+1}+1$，对于 $a_1,a_2,\cdots,a_{n-l}$ 不执行任何操作。
2. 减法操作：对于所有 $i \in [n-l+1,n]$ 的 $a_i$，执行 $a_i-(i+l-n)$ 的操作，其中 $l$ 是小 Z 选择的执行参数，只需要满足 $1\le l \le n$ 的任意整数。换句话说，小 Z 可以选择一个整数 $l\in [1,n]$，然后执行 $a_n-l, a_{n-1}-(l-1),a_{n-2}-(l-2),\cdots, a_{n-l+1}-1$，对于 $a_1,a_2,\cdots,a_{n-l}$ 不执行任何操作。

简单来说，小 Z 可以选择一个数字 $l$, 将 $a_n,a_{n-1},a_{n-2},\cdots,a_{n-l+1}$ 按照顺序依次增加或者减少 $l,l-1,\cdots,1$。

问，小 Z 最少需要执行多少次操作，将数组 $A$ 的所有元素都变为 $0$。

输入格式

一行输入一个整数 $n$ 表示数组长度。

第二行包含 $n$ 个整数 $a_1,a_2,\cdots,a_n$。

输出格式

一行一个整数表示最少的操作次数。

样例

2
-1 3

6

5
1 3 -2 -7 5

26

说明/提示

样例 1 解释

• 选择 $l=1$ 并执行减法操作 $5$ 次，那么数组会变为 $\{-1,-2\}$
• 选择 $l=2$ 并执行加法操作 $1$ 次，数组会变为 $\{0,0\}$

可以证明，这是执行次数最少的方案。

数据范围

测试点 $1-5$：$n\le 10^3$，答案不超过 $10^3$。

测试点 $6-10$：$n\le 10^3$。

测试点 $11-15$：$1\le n \le 2*10^5,-10^{15}\le a_i \le 10^{15}$。