Курси програмування

Limits: 2 sec., 256 MiB

Сьогодні Зеник зрозумів, що не годиться у 2018 році не вміти програмувати. Тож наш герой вирішив також увійти в ІТ. Для цього він хоче пройти \(n\) онлайн-курсів програмування.

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

Тепер Зеник хоче бачити прогрес у проходженні курсів. Він вважає, що прогрес помітний, якщо його оцінка за \((k+1)\)-ий курс більша за оцінку за \(k\)-ий курс для всіх \(k\). Тобто оцінка за 2-ий курс більша за оцінку за 1-ий, оцінка за 3-ій більша за оцінку за 2-ий і так далі.

Допоможіть Зенику та знайдіть мінімальну кількість годин, необхідних хлопцю, щоб досягти своєї мети.

Input

У першому рядку задано ціле число \(n\) — кількість курсів.

У другому рядку задано \(n\) цілих чисел \(a_i\) — оцінка за \(i\)-ий курс.

Output

У єдиному рядку виведіть ціле число — мінімальну кількість годин, необхідних Зенику.

Constraints

\(1 \le n \le 10^5\),

\(1 \le a_i \le 10^9\),

для 40% тестів:

\(1 \le n \le 10^3\),

\(1 \le a_i \le 10^3\).

Samples

Input (stdin) сopy	Output (stdout) сopy
4 3 2 7 4	4

Notes

Один із можливих варіантів розвитку подій:

1. Зеник працює над 2-им і 4-им курсами. Його бали тепер [3, 3, 7, 5].

2. Зеник працює над 4-им курсом. Його бали тепер [3, 3, 7, 6].

3. Зеник працює над 1-им, 2-им і 4-им курсами. Його бали тепер [4, 4, 7, 7].

4. Зеник працює над 2-им і 4-им курсами. Його бали тепер [4, 5, 7, 8].