题目描述

有一个砖块消消乐游戏，游戏画面由n列砖组成，每列都有若干块砖，每块砖都是1x1的正方形且砖块之间排列整齐(每块砖的厚度及砖块之间的缝隙忽略不计)。

玩家每次可以按照以下要求，选定一个矩形区域，将该矩形区域的所有砖块消除。

1）该矩形区域内每块砖都是完整的，即不能选定某块砖的一部分；

例如：可以选定下方左图中的矩形区域(绿色框)，不可以选定下方右图中的矩形区域(红色框)。

2）该矩形区域内不能有空白部分。

例如：不可以选定下图中的矩形区域(红色框)。

给定砖的列数n，以及从左至右每列砖的砖块数量，请计算消除完所有砖块最少需要选定多少次矩形区域。

例如：n=3；从左至右3列砖的砖块数量分别是2、3、2，将所有砖块全部消除最少需要选定2次。

第1次，选定绿色框的矩形区域，将6块砖消除，剩余1块砖:

第2次，选定剩余的1块砖并消除。

输入描述

第一行输入一个整数$n(1 ≤ n ≤ 10^5)$，表示有多少列砖；

第二行输入$n$个整数$(1≤整数≤100)$，分别表示从左至右每列砖的砖块数量，整数之间以一个空格隔开。

输出描述

输出一个整数，表示消除完所有砖块最少需要选定多少次矩形区域。

样例

3
2 3 2

2

提示

本题共10组测试用例，每通过一组用例得 10 分。