CF448C.Painting Fence

Bizon the Champion isn't just attentive, he also is very hardworking.

Bizon the Champion decided to paint his old fence his favorite color, orange. The fence is represented as n vertical planks, put in a row. Adjacent planks have no gap between them. The planks are numbered from the left to the right starting from one, the i-th plank has the width of 1 meter and the height of a__i meters.

Bizon the Champion bought a brush in the shop, the brush's width is 1 meter. He can make vertical and horizontal strokes with the brush. During a stroke the brush's full surface must touch the fence at all the time (see the samples for the better understanding). What minimum number of strokes should Bizon the Champion do to fully paint the fence? Note that you are allowed to paint the same area of the fence multiple times.

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

冠军比松决定将他那面旧篱笆涂成自己最喜欢的颜色——橙色。这面篱笆由 n 块竖直的木板组成，自左至右排成一排，相邻木板之间没有缝隙。木板从左至右编号，编号从 1 开始；第 i 块木板的宽度为 1 米，高度为 a__i 米。

冠军比松在商店购买了一把宽度为 1 米的刷子。他可以用该刷子进行竖直方向或水平方向的涂刷。每次涂刷时，刷子的整个表面必须始终与篱笆接触（参见样例以更好理解）。那么，冠军比松最少需要多少次涂刷才能将整面篱笆完全涂满？注意：允许对篱笆的同一区域重复涂刷。

The first line contains integer n (1 ≤ n ≤ 5000) — the number of fence planks. The second line contains n space-separated integers _a_1, _a_2, ..., a__n (1 ≤ a__i ≤ 109).

第一行包含一个整数 $ n $（$ 1 \leq n \leq 5000 $）—— 表示栅栏木板的数量。
第二行包含 $ n $ 个用空格分隔的整数 $ a_1, a_2, \ldots, a_n $（$ 1 \leq a_i \leq 10^9 $）。

Print a single integer — the minimum number of strokes needed to paint the whole fence.

输出一个整数——涂满整个栅栏所需的最少笔画数。

In the first sample you need to paint the fence in three strokes with the brush: the first stroke goes on height 1 horizontally along all the planks. The second stroke goes on height 2 horizontally and paints the first and second planks and the third stroke (it can be horizontal and vertical) finishes painting the fourth plank.

In the second sample you can paint the fence with two strokes, either two horizontal or two vertical strokes.

In the third sample there is only one plank that can be painted using a single vertical stroke.

在第一个样例中，你需要用画笔分三步涂刷栅栏：第一步为水平方向、高度为 1 的涂刷，覆盖所有木板；第二步为水平方向、高度为 2 的涂刷，覆盖第一和第二块木板；第三步（可以是水平或垂直方向）完成第四块木板的涂刷。

在第二个样例中，你可以用两步完成栅栏的涂刷，这两步既可以均为水平方向，也可以均为垂直方向。

在第三个样例中，仅有一块木板，可用一次垂直方向的涂刷完成。