Нещодавно Козак Вус дізнався про цікаву місцевість, що зветься Поле чудес, на якій ростуть дерева з грошима. Він вирішив посадити n монетних дерев, а наступного року зібрати врожай.
Коли Вус повернувся на Поле чудес з інспекцію, він дізнався, що на кожному дереві виросла принаймні одна монета, при чому кількість монет на i-тому дереві дорівнює ai. Вирішивши, що самому збирати врожай буде надто довго, він побудував машину, яка може деяку кількість разів виконувати наступну операцію:
Вибрати деяке додатне число k;
Знайти перше дерево (дерево з найменшим індексом), на якому на цей час хоча б k монет;
Забрати з нього k монет.
Але в посібнику з доглядом за монетними деревами Козак Вус дізнався, що після збору врожаю на кожному дереві повинна залишитись хоча б одна монета, бо інакше вони не дадуть врожай наступного року.
Тепер Козак Вус цікавиться, який максимальний врожай може зібрати машина після деякої кількості операцій.
Зверніть увагу, що число k може відрізнятись для різних операцій.
Перший рядок містить одне ціле число n (1≤n≤106) — кількість дерев на Полі чудес.
Другий рядок містить n цілих чисел a1,a2,…,an (1≤ai≤109) — початкові кількості монет на деревах.
Виведіть єдине ціле число — максимальна кількість монет, яку може зібрати машина після певної послідовності операцій так, щоб на кожному дереві залишилась прийнамні одна монета.
У другому прикладі неможливо вибрати таке k, щоб зібрати хоча б одну монету і залишити при цьому монети на кожному дереві.
(4 бали): n=2;
(8 балів): n=3;
(7 балів): ai≤2;
(13 балів): ai≤3;
(7 балів): 10≤ai;
(19 балів): ai,n≤1000;
(42 бали): без додаткових обмежень.