冠军比松不仅细心，而且非常勤奋。

冠军比松决定用他最喜欢的颜色橙色来涂刷他的旧篱笆。篱笆被表示为 n 个垂直的木板，排成一排。相邻的木板之间没有间隙。木板从左到右编号，从一开始，第 i 块木板的宽度为 1 米，高度为 a i 米。

冠军比松在商店买了一把刷子，刷子的宽度为 1 米。他可以用刷子进行垂直和水平划痕。在划痕过程中，刷子的整个表面必须始终接触篱笆（请参见示例以更好理解）。冠军比松需要做多少最少次划痕才能完全涂刷整个篱笆？请注意，允许多次涂刷篱笆的同一区域。

n<=5000,ai<=1e9