Минимум увеличений

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

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

Первая строка содержит число $n(n\le 10^6)$. Вторая строка содержит $n$ натуральных чисел, каждое из которых не больше $10^6$.

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

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

Примеры

В первом тесте массив следует преобразовать в $89101112$, выполнив $(8-3)+(9-6)+(10-4)+(11-11)+(12-5)=5+3+6+0+7=21$ операцию.