Covering the North Face

The east district of Byteburg is famous for its long row of buildings constructed with the old architecture, where each building touches its neighbour with no gaps. The north face of these buildings forms a unique silhouette of varying heights. The mayor, Byteasar, wants to cover this north face completely with rectangular posters. Each poster must have vertical and horizontal sides, must be placed so that it entirely adjoins the walls of one or several contiguous buildings, and posters may touch (share edges) but they may not overlap.

Your task is to determine the minimum number of posters required to completely cover the north face of the buildings. A poster covers a rectangular area and must exactly cover a section of the building wall(s).

Hint (Algorithm): You can solve this problem using a stack. Process the building heights one by one. For each height \(h\), while the stack is non-empty and the top is greater than \(h\), pop from the stack. If the stack is non-empty and the top equals \(h\) then do nothing; otherwise if \(h > 0\) push \(h\) onto the stack and increase your poster count by one.

This approach is optimal with an overall time complexity of \(O(n)\).

inputFormat

The first line contains an integer \(n\) (where \(1 \leq n \leq 10^5\)), representing the number of buildings. The second line contains \(n\) space-separated non-negative integers representing the heights of the buildings from east to west.

outputFormat

Output a single integer: the minimum number of posters required to cover the north face of the buildings.

sample

5
1 1 1 1 1

1