eolymp
Competitions

Ukrainian Olympiad in Informatics, III Stage, II Round

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

Нещодавно Козак Вус дізнався про цікаву місцевість, що зветься Поле чудес, на якій ростуть дерева з грошима. Він вирішив посадити $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}
Time limit 2 seconds
Memory limit 256 MiB
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
Author Andrey Abdulaev