Background

NOIP 2018 Senior D1T1.

Problem Description

Chunchun is a road engineer responsible for paving a road of length $n$.

The main task of paving is to fill the sunken ground surface. The whole road can be seen as $n$ consecutive segments connected end to end. Initially, the sinking depth of the $i$-th segment is $d_i$.

Each day, Chunchun can choose a continuous interval $[L,R]$ and fill every segment in this interval, reducing its sinking depth by $1$. When choosing an interval, it must be guaranteed that, before filling, the sinking depth of every segment in the interval is not $0$.

Chunchun wants you to help design a plan that turns the sinking depths of the entire road into $0$ in the shortest time.

Input Format

The input file contains two lines. The first line contains an integer $n$, representing the length of the road. The second line contains $n$ integers separated by a single space; the $i$-th integer is $d_i$.

Output Format

The output file contains only one integer, which is the minimum number of days needed to complete the task.

6   
4 3 2 5 3 5 

9

Hint

【Sample Explanation】

One possible optimal plan is to choose, in order: $[1,6]$, $[1,6]$, $[1,2]$, $[1,1]$, $[4,6]$, $[4,4]$, $[4,4]$, $[6,6]$, $[6,6]$.

【Constraints】

For $30\%$ of the testdata, $1 \le n \le 10$. For $70\%$ of the testdata, $1 \le n \le 1000$. For $100\%$ of the testdata, $1 \le n \le 100000$, $0 \le d_i \le 10000$.

Translated by ChatGPT 5