C. Соня и задача без легенды
ограничение по времени на тест
5 секунд
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Сова Соня не придумала легенду к этой задаче и просто написала вам формальное условие.

Дан массив длины n, содержащий целые положительные числа. За одну операцию можно увеличить или уменьшить на 1 любое число в массиве. Требуется сделать массив строго возрастающим за минимальное количество операций. Числа можно изменять произвольным образом, в том числе они могут стать отрицательными или равными 0.

Входные данные

Первая строка входных данных содержит единственное число n (1 ≤ n ≤ 3000) — длину массива.

Следующая строка содержит n целых чисел ai (1 ≤ ai ≤ 109).

Выходные данные

Выведите одно число — минимальное количество операций, которое потребуется применить, чтобы массив стал строго возрастающим.

Примеры
Входные данные
7
2 1 5 11 5 9 11
Выходные данные
9
Входные данные
5
5 4 3 2 1
Выходные данные
12
Примечание

В первом примере массив после изменений будет выглядеть так:

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