P15034 [UOI 2021 II Stage] Land of Miracles

Recently, Cossack Moustache heard about an interesting place called the Land of Miracles, where trees grow with money on them. He decided to plant $n$ money trees and harvest them in the second year. When Moustache returned to the Land of Miracles for an inspection, he found that each tree had grown at least one coin, and the number of coins on the $i$-th tree was $a_i$. He felt that harvesting by hand would take too much time, so he built a machine. The machine can perform the following operation multiple times: - Choose a positive integer $k$. - Find the first tree (i.e., the one with the smallest index) whose current number of coins is at least $k$. - Take away $k$ coins from that tree. However, in the money tree maintenance manual, Cossack Moustache learned that after harvesting, each tree must have at least one coin left; otherwise, they will not bear fruit next year. Now Cossack Moustache wants to know: after some number of operations, what is the maximum number of coins this machine can harvest. Note that the chosen number $k$ may be different in different operations.

The first line contains an integer $n$ ($1 \leq n \leq 10^6$) — the number of trees in the Land of Miracles. The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \leq a_i \leq 10^9$) — the initial number of coins on the trees.

Output one integer — the maximum number of coins the machine can collect after a sequence of operations, while ensuring that each tree has at least one coin left.

### Sample Explanation In the second sample, it is impossible to choose a $k$ such that at least one coin can be collected, while still leaving a coin on every tree. ### Scoring Rules - (4 points): $n = 2$. - (8 points): $n = 3$. - (7 points): $a_i \leq 2$. - (13 points): $a_i \leq 3$. - (7 points): $10 \leq a_i$. - (19 points): $a_i, n \leq 1\,000$. - (42 points): No additional constraints. Translated by DeepSeek V3. Translated by ChatGPT 5