## COCI '17 Contest 4 #5 Krov

View as PDF

Points: 15 (partial)
Time limit: 1.5s
Memory limit: 128M

Problem type

You are given a histogram consisting of columns of heights , respectively. The histogram needs to be transformed into a roof using a series of operations. A roof is a histogram that has the following properties:

• A single column is called the top of the roof. Let it be the column at position .
• The height of the column at position is .
• All heights are positive integers.

An operation can be increasing or decreasing the heights of a column of the histogram by . It is your task to determine the minimal number of operations needed in order to transform the given histogram into a roof.

#### Input Specification

The first line of input contains the number , the number of columns in the histogram. The following line contains numbers , the initial column heights.

#### Output Specification

You must output the minimal number of operations from the task.

#### Scoring

In test cases worth 60% of total points, it will hold .

#### Sample Input 1

4
1 1 2 3

#### Sample Output 1

3

#### Explanation for Sample Output 1

​By increasing the height of the second, third, and fourth column, we created a roof where the fourth column is the top of the roof.

#### Sample Input 2

5
4 5 7 2 2

#### Sample Output 2

4

#### Explanation for Sample Output 2

By decreasing the height of the third column three times, and increasing the height of the fourth column, we transformed the histogram into a roof. The example is illustrated below. #### Sample Input 3

6
4 5 6 5 4 3

#### Sample Output 3

0