P5019 [NOIP 2018 Senior] Road Paving.

NOIP 2018 Senior D1T1.

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.

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$.

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

【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