## DMOPC '20 Contest 1 P3 - Victor's Algorithm

View as PDF

Points: 7 (partial)
Time limit: 0.6s
Memory limit: 256M

Author:
Problem type

I can sort in ~ Victor, 2019

Victor has invented a brand new sorting algorithm that promises an upper bound! However, there is a catch: this algorithm will only work on a nice sequence of numbers. Victor considers a sequence of length nice if it is first non-decreasing, then non-increasing. (i.e. is nice if there exists some position in the sequence such that ).

You have subsequently found that Victor's algorithm can be extended to any arbitrary sequence of numbers by converting that sequence of numbers into a nice sequence , such that for all . Sadly, because counting is very difficult, you can only tell Victor to increment one element in the sequence by once a second.

Write a program that finds the minimum number of seconds required to convert any given into a valid !

#### Constraints

for all .

##### Subtask 1 [20%]

The length of the sequence is bounded by .

##### Subtask 2 [80%]

The length of the sequence is bounded by .

#### Input Specification

The first line will contain , the length of the sequence.

The next line will contain space-separated integers .

#### Output Specification

Output the minimum number of seconds required to convert the given sequence into a nice sequence.

#### Sample Input 1

10
-6 8 6 -1 3 -8 -6 -2 5 -2

#### Sample Output 1

39

#### Explanation of Sample Output 1

We can make this a nice sequence by incrementing by , by , by , by , and by . Since , the answer is . It can be shown that this is the minimum possible answer.

#### Sample Input 2

5
1 2 3 4 5

#### Sample Output 2

0

#### Explanation of Sample Output 2

This is already a nice sequence.

#### Sample Input 3

7
7 6 5 -1 -3 -4 -5

#### Sample Output 3

0