题目描述

给你一个长度为$\red{n}$的整型数组$\red{a_1,a_2,...,a_n,}$你可以进行一下三种操作：

$\red{1}$、选择一个下标$\red{i，}$将数组第$\red{1}$到$\red{i}$个数减$\red{1}$

$\red{2}$、选择一个下标$\red{i，}$将数组第$\red{i}$到$\red{n}$个数减$\red{1}$

$\red{3}$、将数组所有数都加$\red{1}$

最少需要多少步能将数组的所有数都变为$\red{0}$呢？

输入格式

一行输入$\red{1}$个整数$\red{n}$

下面$\red{n}$个数表示数列

输出格式

输出一个整数表示最少多少次操作。

样例

输入样例

4
4 -4 4 -4

输出样例

36

提示

对于$\red{40\%}$的数据 $\red{n<=1000}$

对于$\red{100\%}$的数据 $\red{1<=n<=200000,-10^9<=a_i<=10^9}$