e-olymp
favorite Нам необхідно трохи Вашої допомоги щоб сайт продовжував працювати, натисніть на банер щоб дізнатись більше.
Змагання

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}
Ліміт часу 2 секунди
Ліміт використання пам'яті 256 MiB
Вхідні дані #1
4
1 4 2 3
Вихідні дані #1
3
Вхідні дані #2
6
1 2 2 3 4 2
Вихідні дані #2
0
Автор Andrey Abdulaev