Score : 1500 points
We have a sequence A of length N.
On this sequence, we can perform the following two kinds of operations:
Swap two adjacent elements.
Select one element, and increment it by 1.
We will repeatedly perform these operations so that A will be a non-decreasing sequence. Find the minimum required number of operations.
Input is given from Standard Input in the following format:
N A_1 A_2 : A_N
Print the minimum number of operations required to turn A into a non-decreasing sequence.
5 4 1 8 8 7
2
We can turn A into a non-decreasing sequence in two operations:
20 8 2 9 7 4 6 7 9 7 4 7 4 4 3 6 2 3 4 4 9
62