Minimum Brush Strokes to Paint a Fence
Given a fence of n vertical planks with varying heights, determine the minimum number of horizontal and vertical brush strokes (each 1 meter wide) needed to fully paint the entire fence surface.
Question Timeline
See when this question was last asked and where, including any notes left by other candidates.
Late October, 2026
Bob 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 ai meters. Bob bought a brush in the shop, the brush's width is 1 meter. He can only 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 Bob do to fully paint the fence? Note that you are allowed to paint the same area of the fence multiple times. Input: The first line contains integer n (1 ≤ n ≤ 5000) — the number of fence planks. The second line contains n space-separated integers a1, a2, ..., an (1 ≤ ai ≤ 10^9). Output: Print a single integer — the minimum number of strokes needed to paint the whole fence. Examples Input: 5 2 2 1 2 1 Output: 3 Input: 2 2 2 Output: 2 Input: 1 5 Output: 1
Hello Interview Premium
Your account is free and you can post anonymously if you choose.