Сова Соня не придумала легенду к этой задаче и просто написала вам формальное условие.
Дан массив длины n, содержащий целые положительные числа. За одну операцию можно увеличить или уменьшить на 1 любое число в массиве. Требуется сделать массив строго возрастающим за минимальное количество операций. Числа можно изменять произвольным образом, в том числе они могут стать отрицательными или равными 0.
Выходные данные
Выведите одно число — минимальное количество операций, которое потребуется применить, чтобы массив стал строго возрастающим.
Примечание
В первом примере массив после изменений будет выглядеть так:
2 3 5 6 7 9 11
|2 - 2| + |1 - 3| + |5 - 5| + |11 - 6| + |5 - 7| + |9 - 9| + |11 - 11| = 9
Во второй примере так:
1 2 3 4 5
|5 - 1| + |4 - 2| + |3 - 3| + |2 - 4| + |1 - 5| = 12
Примеры
| № | Входные данные | Выходные данные |
|
1
|
7
2 1 5 11 5 9 11
|
9
|
|
2
|
5
5 4 3 2 1
|
12
|