题目描述

这天，小明在砍竹子，他面前有 n 棵竹子排成一排，一开始第 i 棵竹子的高度为 hi. 他觉得一棵一棵砍太慢了，决定使用魔法来砍竹子。 魔法可以对连续的一段相同高度的竹子使用，假设这一段竹子的高度为H， 那么使用一次魔法可以把这一段竹子的高度都变为：

其中 ⌊x⌋ 表示对 x 向下取整。

小明想知道他最少使用多少次魔法可以让所有的竹子的高度都变为1。

输入格式

第一行为一个正整数 n，表示竹子的棵数。 第二行共 n 个空格分开的正整数 hi，表示每棵竹子的高度。 20%的测试数据：n ≤ 1000; hi ≤ 10^6。 100%的测试数据：n ≤ 2 × 10^5; hi ≤ 10^18。

输出格式

一个整数表示答案。

输入样例

6
2 1 4 2 6 7

输出样例

5

数据范围与提示

其中一种方案： 2 1 4 2 6 7 → 2 1 4 2 6 2 → 2 1 4 2 2 2 → 2 1 1 2 2 2 → 1 1 1 2 2 2 → 1 1 1 1 1 1 共需要 5 步完成。