说明

码头上有一批货物，它们被摆放成了n摞，每摞的个数(高度)为di，并排成一排。

现在包工头酋长想用一台特殊的搬运机，用最少的次数，将这批货物全部取走。

这台搬运机的工作原理是：一次可以取走相邻几排最下面一层的所有货物。

例如：当货物共有4摞，每摞高度分别为 2 3 1 2 时，我们可以采用如下策略使得总使用次数最少

第一步：由于四摞货物是相邻的，取走这四摞货物最下面的一排货物，当前变为 1 2 0 1

第二步：此时第三摞货物取空，第一、二摞和第四摞不相邻，取走前两摞货最下面一排，当前变为 0 1 0 1

第三步、第四步：分别取走第二摞和第四摞货物最下面一排，从而将这批货物全部取走

因此使用这台搬运机的最少次数为：4

输入格式

输入数据包含两行

第一行包括一个整数n, 含义如题面所述 ( 1 <= n <= 100000)

第二行包括n个整数di, 表示每摞货物的高度(个数) (0 <= di <= 10000)

输出格式

输出包含一个整数, 表示使用搬运机的最少次数

样例

4
2 3 1 2

4