Козак Вус та Поле чудес

Нещодавно Козак Вус дізнався про цікаву місцевість, що зветься Поле чудес, на якій ростуть дерева з грошима. Він вирішив посадити $n$ монетних дерев, а наступного року зібрати врожай.

Коли Вус повернувся на Поле чудес з інспекцію, він дізнався, що на кожному дереві виросла принаймні одна монета, при чому кількість монет на $i$-тому дереві дорівнює $a_i$. Вирішивши, що самому збирати врожай буде надто довго, він побудував машину, яка може деяку кількість разів виконувати наступну операцію:

• Вибрати деяке додатне число $k$;

• Знайти перше дерево (дерево з найменшим індексом), на якому на цей час хоча б $k$ монет;

• Забрати з нього $k$ монет.

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

Тепер Козак Вус цікавиться, який максимальний врожай може зібрати машина після деякої кількості операцій.

Зверніть увагу, що число $k$ може відрізнятись для різних операцій.

Input

Перший рядок містить одне ціле число $n$ ($1\le n\le 10^6$) — кількість дерев на Полі чудес.

Другий рядок містить $n$ цілих чисел $a_1,a_2,\dots ,a_n$ ($1\le a_i\le 10^9$) — початкові кількості монет на деревах.

Output

Виведіть єдине ціле число — максимальна кількість монет, яку може зібрати машина після певної послідовності операцій так, щоб на кожному дереві залишилась прийнамні одна монета.

Examples

Note

У другому прикладі неможливо вибрати таке $k$, щоб зібрати хоча б одну монету і залишити при цьому монети на кожному дереві.

Scoring

1. ($4$ бали): $n=2$;

2. ($8$ балів): $n=3$;

3. ($7$ балів): $a_i\le 2$;

4. ($13$ балів): $a_i\le 3$;

5. ($7$ балів): $10\le a_i$;

6. ($19$ балів): $a_i,n\le 1000$;

7. ($42$ бали): без додаткових обмежень.