## NOIP '18 P1 - Paving Roads

View as PDF

Points: 7 (partial)
Time limit: 1.0s
Memory limit: 512M

Problem type

You have an array of length that are initially zero. In each step, you may choose a consecutive interval and increase the values by 1. Find the minimum number of operations required so that the -th entry of the array is equal to .

#### Input Specification

The input file has two lines. The first line has an integer denoting the length of the array. The second line contains integers separated by one space. The -th integer denotes .

#### Output Specification

The output contains only one integer denoting the minimum number of operations required.

#### Sample Input

6
4 3 2 5 3 5

#### Sample Output

9

#### Explanation

One possible optimal solution is to choose as the subintervals to increment.

#### Constraints

For of test data, .
For of test data, .
For of test data, , .