John wants to paint his old fence orange. The fence is made of plankHeights.size() vertical planks arranged in one row with no gaps between adjacent planks. The planks are numbered from left to right starting from 0. Every plank has width 1 meter, and the height of the plank at index i is plankHeights.get(i) meters.

John bought a brush whose width is exactly 1 meter. He can paint the fence using vertical strokes and horizontal strokes. During each stroke, the full surface of the brush must stay in contact with the fence at all times.

It is allowed to paint the same part of the fence more than once. Your task is to calculate the minimum number of strokes required to paint the entire fence completely.

Method Signature

Implement the following method:

int minimumStrokesToPaintFence(List<Integer> plankHeights)

Method Description

The method receives the heights of all fence planks and returns the minimum number of brush strokes needed to fully paint the fence.

• plankHeights.get(i) represents the height of the plank at zero-based index i.
• A vertical stroke can paint one complete plank from bottom to top.
• A horizontal stroke can paint one unit-height layer across a continuous segment of planks, as long as every plank in that segment has height at least that layer.
• The same area of the fence may be painted multiple times.
• The output must be deterministic and must always be the smallest possible number of strokes.

Constraints

• 1 ≤ plankHeights.size() ≤ 5,000
• 1 ≤ plankHeights.get(i) ≤ 1,000,000,000
• plankHeights will not be empty.
• No parameter value will be null.

Return Value

Return one integer, the minimum number of strokes needed to paint the whole fence.

Examples

Example 1

Method call:

minimumStrokesToPaintFence(plankHeights = List.of(3, 1, 2, 2))

Output:

3

Explanation:

One horizontal stroke can paint height 1 across all four planks. Then one vertical stroke can paint the first plank completely, possibly repainting its already painted lower part. One more horizontal stroke can paint the remaining height on the planks at indices 2 and 3. So the minimum number of strokes is 3.

Example 2

Method call:

minimumStrokesToPaintFence(plankHeights = List.of(5, 5, 5))

Output:

3

Explanation:

The fence can be painted using three vertical strokes, one for each plank. Using horizontal strokes would require 5 strokes, so the minimum answer is 3.

Example 3

Method call:

minimumStrokesToPaintFence(plankHeights = List.of(1, 2, 3, 2, 1))

Output:

3

Explanation:

One horizontal stroke can paint height 1 across all planks. Another horizontal stroke can paint height 2 across the planks at indices 1, 2, and 3. A final stroke paints the remaining part of the middle plank. Therefore, the answer is 3.

Example 4

Method call:

minimumStrokesToPaintFence(plankHeights = List.of(10))

Output:

1

Explanation:

Since there is only one plank, one vertical stroke is enough to paint the complete fence.