为了庆祝在 NlogNsglow 举办的算法运动会盛大开幕，一排大楼将被拆除，以展现焕然一新的面貌。最初的计划是通过控制爆破来完成，每栋大楼进行一次爆破，但由于时间紧迫，现在需要一个更快速的解决方案。

来自维基百科，根据知识共享许可协议发布，作者 G Laird

为了帮助你更快地拆除这些大楼，你被允许使用一台通用动能/炽能粒子炮（UKIEPC）。每次装药发射，这台尖端设备可以执行以下两种操作之一：

• 拆除单栋大楼中的所有楼层。
• 同时拆除所有大楼中的第 $x$ 层（$x$ 由用户指定）。在这种情况下，高度小于 $x$ 层的大楼将保持原样；而对于高度大于 $x$ 层的大楼，被拆除的第 $x$ 层之上的所有楼层都会向下塌陷一级。

任务

给定所有大楼的楼层数，输出清除所有大楼的所有楼层所需的最小装药次数。

输入格式

第一行输入包含大楼的数量 $n$，其中 $2 \le n \le 100\,000$。

第二行包含 $n$ 个连续的大楼高度 $h_i$（对于 $i = 1, 2, \dots, n$），其中 $1 \le h_i \le 1\,000\,000$。

输出格式

输出一行，包含一个整数：拆除所有大楼所需的最小装药次数。

样例

输入样例 1

6
2 1 8 8 2 3

输出样例 1

5

输入样例 2

5
1 1 1 1 10

输出样例 2

2