Save the World with Brush Strokes

In an unknown worldline, Okren receives a mysterious dmail about an impending cataclysm: because he missed a date with his assistant, the worldline will undergo an irreversible change. Before his date, he was forced by his landlord to quickly color a portrait to pay overdue rent—and his delay cost him dearly. Now, the fate of the world rests on you! Though neither of you are skilled painters, you can use programming as your brush.

The painting consists of N contiguous rectangles, where the i-th rectangle has a width of 1 and a height of \(H_i\). Initially, every rectangle is uncolored. You have a brush of width 1 that you can use in one of two ways:

• Vertical Stroke: Paint a vertical segment completely inside a single rectangle.
• Horizontal Stroke: Paint a horizontal segment across one or more adjacent rectangles. The stroke must lie completely inside the rectangles (i.e. it cannot extend outside the boundaries) and must be drawn in a straight line.

Each stroke, whether vertical or horizontal, takes exactly 1 unit of time regardless of its length. Your task is to compute the minimum time required to fully color all rectangles.

You might find it useful to think of the problem recursively. For an interval of rectangles from l to r and a current painted base level, one strategy is to either paint each rectangle individually (a vertical stroke per rectangle) or to perform a horizontal stroke at the minimum unpainted height over the interval and then solve the subintervals above that stroke. Formally, define a function:

[ f(l, r, b) = \min( (r - l + 1),; (m - b) + \sum_{\text{subinterval } [i, j] \text{ with } H_k > m} f(i, j, m) ) ]

where \(m = \min_{l \le k \le r} H_k\) and b is the base (already painted) height. Initially, \(b = 0\). The answer is then \(f(1, N, 0)\).

inputFormat

The first line contains a single integer N (\(1 \le N \le 10^5\)) representing the number of rectangles. The second line contains N integers \(H_1, H_2, \ldots, H_N\) (\(1 \le H_i \le 10^9\)) where \(H_i\) is the height of the i-th rectangle.

outputFormat

Output a single integer representing the minimum time necessary to completely color all rectangles.

sample

3
1 2 3

3