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 subtasks:
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
Comments
Since the original data were weak, three additional test cases were added, and all submissions were rejudged.
This problem is missing the test cases where max is the first or the last element, for example, 7 5 4 5 6.