Problems
Козак Вус та Поле чудес
Козак Вус та Поле чудес
Нещодавно Козак Вус дізнався про цікаву місцевість, що зветься Поле чудес, на якій ростуть дерева з грошима. Він вирішив посадити $n$ монетних дерев, а наступного року зібрати врожай.
Коли Вус повернувся на Поле чудес з інспекцію, він дізнався, що на кожному дереві виросла принаймні одна монета, при чому кількість монет на $i$-тому дереві дорівнює $a_i$. Вирішивши, що самому збирати врожай буде надто довго, він побудував машину, яка може деяку кількість разів виконувати наступну операцію:
\begin{itemize}
\item Вибрати деяке додатне число $k$;
\item Знайти перше дерево (дерево з найменшим індексом), на якому на цей час хоча б $k$ монет;
\item Забрати з нього $k$ монет.
\end{itemize}
Але в посібнику з доглядом за монетними деревами Козак Вус дізнався, що після збору врожаю на кожному дереві повинна залишитись хоча б одна монета, бо інакше вони не дадуть врожай наступного року.
Тепер Козак Вус цікавиться, який максимальний врожай може зібрати машина після деякої кількості операцій.
Зверніть увагу, що число $k$ може відрізнятись для різних операцій.
\InputFile
Перший рядок містить одне ціле число $n$ ($1 \leq n \leq 10^6$) --- кількість дерев на Полі чудес.
Другий рядок містить $n$ цілих чисел $a_1, a_2, \ldots, a_n$ ($1 \leq a_i \leq 10^9$) --- початкові кількості монет на деревах.
\OutputFile
Виведіть єдине ціле число --- максимальна кількість монет, яку може зібрати машина після певної послідовності операцій так, щоб на кожному дереві залишилась прийнамні одна монета.
\Note
У другому прикладі неможливо вибрати таке $k$, щоб зібрати хоча б одну монету і залишити при цьому монети на кожному дереві.
\Scoring
\begin{enumerate}
\item ($4$ бали): $n=2$;
\item ($8$ балів): $n=3$;
\item ($7$ балів): $a_i \leq 2$;
\item ($13$ балів): $a_i \leq 3$;
\item ($7$ балів): $10 \leq a_i$;
\item ($19$ балів): $a_i, n \leq 1\,000$;
\item ($42$ бали): без додаткових обмежень.
\end{enumerate}
Input example #1
4 1 4 2 3
Output example #1
3
Input example #2
6 1 2 2 3 4 2
Output example #2
0