시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1.5 초 | 128 MB | 40 | 26 | 21 | 65.625% |
You are given a histogram consisting of N columns of heights X1, X2, … XN, 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:
An operation can be increasing or decreasing the heights of a column of the histogram by 1. It is your task to determine the minimal number of operations needed in order to transform the given histogram into a roof.
The first line of input contains the number N (1 ≤ N ≤ 105), the number of columns in the histogram.
The following line contains N numbers Xi (1 ≤ Xi ≤ 109), the initial column heights.
You must output the minimal number of operations from the task.
4 1 1 2 3
3
5 4 5 7 2 2
4
6 4 5 6 5 4 3
0
Clarification of the first test case: 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.
Clarification of the second test case: 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.