Minimum Days to Repair the Road

ChunChun is a road engineer tasked with repairing a road of length \( n \). The road is divided into \( n \) consecutive segments. Initially, the \( i^{th} \) segment has a sinking depth of \( d_i \). Each day, ChunChun can choose a contiguous segment \( [L, R] \) and fill each segment in that interval, reducing its sinking depth by \( 1 \). However, the chosen segment must satisfy that every segment in \( [L, R] \) has a sinking depth greater than \( 0 \) before the filling operation.

Your task is to help ChunChun design a strategy to reduce all sinking depths to \( 0 \) in the minimum number of days.

Hint: It can be shown that the minimum number of days required is given by:

[ d = d_1 + \sum_{i=2}^{n} \max(0, d_i - d_{i-1}) ]

where \( d_1, d_2, \ldots, d_n \) are the initial sinking depths (with \( d_0 \) assumed to be \( 0 \)).

inputFormat

The first line contains an integer \( n \) (the number of segments). The second line contains \( n \) space-separated integers \( d_1, d_2, \ldots, d_n \) indicating the initial sinking depths of the segments.

outputFormat

Output a single integer representing the minimum number of days required to reduce all sinking depths to \( 0 \).

sample

3
2 1 3

4