eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Мінімум збільшень

Мінімум збільшень

Ліміт часу 3 секунди
Ліміт використання пам'яті 128 MiB

Дано масив, що складається з n натуральних чисел. Знайдіть найменшу кількість операцій, за допомогою яких його можна перетворити в арифметичну прогресію з різницею 1. Одна операція — це збільшення будь-якого элемента на 1.

Вхідні дані

Перший рядок містить число n~(n \le 10^6). Другий рядок містить n натуральних чисел, кожне з яких не перешищує 10^6.

Вихідні дані

Виведіть найменшу кількість операцій, за допомогою яких можна перетворити масив в арифметичну прогресію з різницею 1.

Приклад

В першому тесті тесті масив варто перетворитив 8~9~10~11~12, виконавши (8 - 3) + (9 - 6) + (10 - 4) + (11 - 11) + (12 - 5) = 5 + 3 + 6 + 0 + 7 = 21 операцій.

Вхідні дані #1
5
3 6 4 11 5
Вихідні дані #1
21
Вхідні дані #2
5
4 4 5 5 7
Вихідні дані #2
5