Дано масив із ~N~ цілих чисел. За одну операцію ви можете вибрати будь-який елемент і збільшити його на ~1~ (операцію можна виконувати будь-яку кількість разів для будь-яких елементів).

Знайдіть мінімальну загальну кількість операцій, щоб масив став строго зростаючим, тобто ~a_1 < a_2 < \dots < a_N~.

Вхідні дані

Перший рядок містить ціле число ~N~ (~1 \le N \le 100\,000~).

Другий рядок містить ~N~ цілих чисел ~a_1, a_2, \dots, a_N~ (~1 \le a_i \le 10^9~).

Вихідні дані

Виведіть одне ціле число — мінімальну кількість операцій.

Приклад

Вхідні дані

4
1 2 1 3

Вихідні дані

3

Пояснення: один із оптимальних способів — збільшити третій елемент на ~2~ (стає ~3~) і четвертий на ~1~ (стає ~4~). Отримаємо масив ~[1, 2, 3, 4]~.