样例下载

题目描述

$N$ 个整数从左向右排成一排，从左到右数第 $i$ 个整数是 $X_i$。

你可以进行以下操作：

选择位于最右端的 $K$ 个数，对这 $K$ 个数全部进行加法（或全部进行减法）运算，要求对于这 $K$ 个数从左到右数的第 $j (1 ≤ j ≤ K)$ 个数执行 $+j$ （或$-j$）的运算。

你可以操作任意次，每次的 $K (1 ≤ K ≤ N)$ 值由你决定，每次的运算是全加还是全减也由你决定。

你的目标是把所有数字全部变为 0.

问：你最少需要操作多少次？

输入格式

第一行：一个整数 $N$。

第二行：$N$ 个整数 $X_i$。

输出格式

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

样例输入

4
0 1 2 -3

样例输出

7

样例解释

初始时：序列 A={0, 1, 2, -3}

第一次操作：K=3，减法：A={0, 1-1=0, 2-2=0, -3-3=-6}={0,0,0,-6}

接下来 6 次操作，每次 K=1，加法，最后全部清零。

数据范围

100% 的数据：$1 ≤ N ≤ 2·10^5$, $|X_i|≤ 10^{15}$，数据保证答案 $≤ 10^9$。其中

• 30% 的数据：$N ≤ 10^3$，数据保证答案 $≤ 10^3$。
• 30% 的数据：$N ≤ 10^3$，数据保证答案 $≤ 10^9$。