暂无测试数据。

大家都知道 wy 很喜欢养花，她一共养了 $n$ 盆花，这 $n$ 盆花排成一排放在花园中，而 wy 为了方便浇水，专门买了一个自动养花装置。

这个装置非常有趣，除了可以浇花以外，还可以从花盆的土壤里抽出一部分水分，防止浇水太多将花淹死。

但是这个养花装置实在是太重了，wy 没有办法，只能将它放在第 $n$ 盆花之后的位置上。

因此导致一个问题，现在不管是浇水还是抽水的操作，都只能对以 $n$ 为端点的连续一段花盆使用。

比如现在 wy 想要给第 $i$ 盆花浇一次水，这个操作会使得第 $i \sim n$ 盆花都被浇一次水，一次浇水会增加花盆中 $1$ 单位的水量。

同样的，如果 wy 想要给第 $i$ 盆花抽一次水，这个操作会使得第 $i \sim n$ 盆花都被抽一次水，一次抽水会每个花盆中 $1$ 单位的水量。

现在 wy 知道每个花盆中一开始的水量是 $a_i$，这个水量可以是负数，表示这盆花非常缺水。

因为 wy 非常懒，所以她想操作机器让所有花盆中的水量保持一致就可以了，这样她的所有花状态都是一样的，她想知道自己最少需要操作几次装置。

但是 wy 又不好意思特别麻烦你，于是她愿意在开始操作装置之前，亲自动手维护一盆花的水量，也就是说你可以提前让 wy 将某一盆花的水量变成任意数字。

输入格式

输入第一行包含一个整数 $n$ 表示一共有 $n$ 盆花。

接下来包含 $n$ 个整数 $a_i$ 表示每盆花的水量。

输出格式

输出包含一个整数表示最少需要进行操作装置的次数。

数据范围

对于 $20\%$ 的数据，$2 \leq n \leq 100, -100 \leq a_i \leq 100$

对于 $40\%$ 的数据，$2 \leq n \leq 10000, -10000 \leq a_i \leq 10000$

对于 $100\%$ 的数据，$2 \leq n \leq 200000, -10^8 \leq a_i \leq 10^8$

4
99 96 97 95

3