WWOJ--ZCMU测试赛2

Description

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

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

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

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

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

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

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

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

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

Input

输入第一行包含一个整数 $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$

徐老师的养花装置 1540

Description

Input

Output

Samples