有一个长度为 n 的数组。在初始状态下，所有元素都为 0。

每次操作，可以将一个连续的区间 [l, r] 内的所有数加上一个正整数 x，但要求任意两个操作区间要么互不相交，要么一个包含另外一个。

请问能将原数组变为给定数组 a 的最少操作次数。

第一行输入一个正整数 n。

接下来一行输入 n 个非负整数 a_i。

输出最少的操作次数。

样例 2 解释

a = [1,2,3,2,1,3] 可以这样构造（4 次操作）：

• [1,5] 全部加 1，数组变为 [1,1,1,1,1,0]；
• [2,4] 全部加 1，数组变为 [1,2,2,2,1,0]；
• [3,3] 加 1，数组变为 [1,2,3,2,1,0]；
• [6,6] 加 3，数组变为 [1,2,3,2,1,3]。

可以看到四个区间两两之间要么不相交（[6,6] 与其它三个），要么互相包含，满足要求。

数据范围

• 对于 30\% 的数据，n \le 1000；
• 对于 100\% 的数据，n \le 10^5,\ 0 \le a_i \le 10^9。

提示

把数组画成一排柱子，每次操作就是往柱状图里贴一个「高 x、宽 [l,r]」的矩形，而「不相交或包含」正好就是矩形只能上下叠或者左右分开。于是最少操作次数 = 柱状图能被切成的层数。

用一个单调递增栈维护「此刻仍然敞开着的那些层的层级高度」：遇到 a_i 时，先把所有高于 a_i 的层弹掉（它们必然在这一格结束）；若此时栈顶恰好等于 a_i，说明这一层还在延续，不需要新操作；否则（栈空或栈顶更小）就必须新开一层，把答案加一。因为 x 可以任取正整数，从栈顶高度直接抬到 a_i 只需要一次操作。总复杂度 O(n)。