CF448C Painting Fence

Bizon the Champion 不仅细心，而且非常勤奋。 Bizon the Champion 决定将他的旧栅栏粉刷成他最喜欢的颜色——橙色。栅栏表示为 $ n $ 个垂直木板，排成一行。相邻的木板之间没有间隙。木板从左到右从 1 开始编号，第 $ i $ 块木板宽 $ 1 $ 米，高 $ a_i $ 米。 Bizon the Champion 在商店买了一把刷子，刷子的宽度是 $ 1 $ 米。他可以用刷子进行垂直和水平描边。在粉刷过程中，刷子的整个表面必须始终接触栅栏（请参阅示例以更好地理解）。Bizon the Champion 应该粉刷多少次才能完全粉刷栅栏？请注意，您可以多次粉刷栅栏的同一区域。

第一行包含整数 $ n(1\le n \le 5000)$ — 栅栏板的数量。 第二行包含 $ n $ 个空格分隔的整数 $ a_{1},a_{2},\cdots,a_{n} $ $ (1\le a_{i} \le 10^{9}) $ 。

打印一个整数 — 粉刷整个栅栏所需的最少粉刷次数。

在第一个样例中，你需要用刷子分三次粉刷栅栏板:第一次粉刷在高度1上沿着所有栅栏板水平粉刷。第二个笔画在高度2上水平粉刷第一个和第二个栅栏板，第三个笔画(可以是水平的和垂直的)完成第四个栅栏板的粉刷。 在第二个样例中，您可以粉刷两次（两次水平粉刷或两次垂直粉刷）来粉刷栅栏。 在第三个样例中，只有一块栅栏板可以使用刷子单次垂直粉刷进行。