Козак Вус та Поле чудес#10361
Нещодавно Козак Вус дізнався про цікаву місцевість, що зветься Поле чудес, на якій ростуть дерева з грошима. Він вирішив посадити монетних дерев, а наступного року зібрати врожай.
Коли Вус повернувся на Поле чудес з інспекцією, він дізнався, що на кожному дереві виросла принаймні одна монета, причому кількість монет на -тому дереві дорівнює a_i. Вирішивши, що самому збирати врожай буде надто довго, він побудував машину, яка може деяку кількість разів виконувати наступну операцію:
Вибрати деяке додатне число ;
Знайти перше дерево (дерево з найменшим індексом), на якому на цей час хоча б монет;
Забрати з нього монет.
Але в посібнику з догляду за монетними деревами Козак Вус дізнався, що після збору врожаю на кожному дереві повинна залишитись хоча б одна монета, бо інакше вони не дадуть врожай наступного року.
Тепер Козак Вус цікавиться, який максимальний врожай може зібрати машина після деякої кількості операцій.
Зверніть увагу, що число може відрізнятись для різних операцій.
Перший рядок містить одне ціле число (1 \leq n \leq 10^6) — кількість дерев на Полі чудес.
Другий рядок містить цілих чисел a_1, a_2, \ldots, a_n (1 \leq a_i \leq 10^9) — початкові кількості монет на деревах.
Виведіть єдине ціле число — максимальна кількість монет, яку може зібрати машина після певної послідовності операцій так, щоб на кожному дереві залишилась принаймні одна монета.
Приклад 1
Приклад 2
У другому прикладі неможливо вибрати таке , щоб зібрати хоча б одну монету і залишити при цьому монети на кожному дереві.
( бали): n=2;
( балів): n=3;
( балів): a_i \leq 2;
( балів): a_i \leq 3;
( балів): 10 \leq a_i;
( балів): a_i, n \leq 1\,000;
( бали): без додаткових обмежень.