在一个大房间里，有 $N$ 个气球漂浮在空中，从左到右排成一排。年轻的 Perica 喜欢玩箭并练习他的狩猎技巧。他从房间的左侧向右侧射出一支箭，射出时的高度可以任意选择。箭从左向右移动，在选定的高度 $H$ 飞行，直到碰到一个气球。当箭触碰到气球时，气球会爆炸并消失，而箭会继续向右飞行，但高度会降低 $1$。也就是说，如果箭原本在高度 $H$ 飞行，在刺破气球后，它将继续在高度 $H-1$ 飞行。

我们主人公的目标是用尽可能少的箭刺破所有的气球。

输入格式

第一行包含一个整数 $N$ ($1 \le N \le 1\,000\,000$)。

第二行包含一个由 $N$ 个整数组成的数组 $H_i$。

每个整数 $H_i$ ($1 \le H_i \le 1\,000\,000$) 表示从左到右第 $i$ 个气球漂浮的高度。

输出格式

输出的第一行也是唯一的一行，应包含 Pero 刺破所有气球所需射出箭的最少次数。

子任务

对于 $40\%$ 的测试数据，满足 $N \le 5\,000$。

样例

输入样例 1

5
2 1 5 4 3

输出样例 1

2

输入样例 2

5
1 2 3 4 5

输出样例 2

5

输入样例 3

5
4 5 2 1 4

输出样例 3

3

说明

第一个样例的解释：我们的主人公在高度 $5$ 射出一支箭——它销毁了高度为 $[5, 4, 3]$ 的气球；并在高度 $2$ 射出一支箭——它销毁了高度为 $[2, 1]$ 的气球。