涂墙
题目描述
乐乐在涂漆一面墙,这个墙是由很多宽为 1 ,高为 \(h_i\) 的方块构成的,乐乐的刷子宽为 1 ,他只能水平涂,不能竖直涂,涂过的地方可以重复涂。现在他想知道,最少涂多少次可以将这面墙涂完?
输入格式
输入共2行,第一行输入一个正整数 \(n\)
接下来一行输入 \(n\) 个整数 \(h_i\),分别表格每个方块的高度,方块是按次序摆放的。
输出格式
输出最少涂几次
输入输出样例
输入#1
5
2 2 1 2 1
输出#1
3
说明/提示
样例说明:
在最上面先水平涂一次,然后将第一块和第二块方块按水平再涂一次(没涂过的地方),最后将第四块方块按水平涂一次,最少涂 3 次。
数据范围与约定:
\(1\le n\le5\times10^4\),\(1\le h_i\le10^9\)