冠军 Bizon 不仅细心,而且非常勤奋。
冠军 Bizon 决定将他的旧栅栏漆成他最喜欢的颜色,橙色。栅栏由 n 块垂直的木板表示,并排成一排。相邻的木板之间没有间隙。木板从左到右从一块开始编号,第 i 块木板的宽度为 1 米,高度为 ai 米。
Bizon the Champion在商店里买了一把刷子,刷子的宽度是1米。他可以用画笔进行垂直和水平的描画。在笔划过程中,刷子的整个表面必须始终接触栅栏(请参阅示例以更好地理解)。冠军 Bizon 最少需要多少笔才能完全涂满栅栏?请注意,您可以多次绘制栅栏的同一区域。
输入
第一行包含整数 n (1 ≤ n ≤ 5000) — 栅栏板的数量。第二行包含 n 个空格分隔的整数 a1, a2, ..., an (1 ≤ ai ≤ 109)。
输出
打印一个整数 - 绘制整个栅栏所需的最少笔划数。
示例
输入 #1
5 2 2 1 2 1
输出 #1
3
输入 #2
2 2 2
输出 #2
2
输入 #3
1 5
输出 #3
1
注意
在第一个示例中,您需要用画笔分三笔绘制栅栏:第一笔沿着所有木板水平地在高度 1 上进行。第二笔画水平地在高度 2 上进行,并绘制第一块和第二块木板,第三笔画(可以是水平的和垂直的)完成第四块木板的绘制。
在第二个示例中,您可以使用两个笔画(两个水平笔画或两个垂直笔画)绘制栅栏。
在第三个示例中,只有一块木板可以使用单个垂直笔画进行绘制。