该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

码头上有一批货物，它们被摆放成 $n$ 摞，每摞的个数（高度）为 $d_i$，并排成一排。

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

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

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

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

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

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

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

输入格式

输入数据包含两行。

第一行包括一个整数 $n$，含义如题面所述 （ $1 \le n \le 100000$）。

第二行输入 $n$ 个整数 $d_i$，表示每摞货物的高度（$0 \le d_i \le 10000$）。

输出格式

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

样例

4
2 3 1 2

4