丁丁（Tinky Winky）在神奇岛（Tubbytronic Superdome）留下了一个由 $n$ 个零组成的序列，然后和迪西（Dipsy）一起出去散步了。当他回来时，他发现发生了一件糟糕的事。序列被修改了，而小波（Po）正躲在房间角落里调皮地微笑。

“天哪！小波，你干了什么？！”丁丁惊恐地问。

“我把序列升级了！”小波回答道。

经过一番盘问，大家得知小波对序列进行了一些“升级”操作。在每次升级中，她会选择序列的一个区间，并将该区间内的所有元素都增加某个正整数。此外，任意两个选择的区间要么完全不相交，要么其中一个完全包含在另一个之中。

“你一共进行了多少次升级，小波？”拉拉（Laa-Laa）询问道。

“我真的不知道！我唯一能确定的是，我用了最少的操作次数来得到这个序列！”小波精疲力竭地说道。

“那肯定就是 $m$ 次了！”努努（Noo-Noo，天线宝宝的吸尘器宠物）宣布道。

努努说的数字 $m$ 是多少？

输入格式

第一行包含一个整数 $n$（$1 \le n \le 100\,000$），表示序列的长度。

第二行包含 $n$ 个非负整数 $a_i$（$0 \le a_i \le 10^9$），表示小波升级后的序列。

输出格式

输出 $m$，即最少可能的操作次数。

子任务

对于 $30\%$ 的数据，满足 $1 \le n \le 1000$。

样例

输入样例 1

3
2 2 2

输出样例 1

1

输入样例 2

5
2 3 3 3 2

输出样例 2

2

输入样例 3

6
1 2 3 2 1 3

输出样例 3

4

说明

样例 2 解释

小波首先将整个序列的所有元素增加 $2$，然后将中间的三个元素增加 $1$。