Cossack Vus and the Field of Wonders#10361
Cossack Vus recently discovered a fascinating place called the Field of Wonders, where trees that grow coins can be found. He decided to plant coin trees and planned to harvest them the following year.
Upon returning to the Field of Wonders for an inspection, Vus found that each tree had grown at least one coin, with the -th tree having a_i coins. Realizing that harvesting the coins manually would be too time-consuming, he constructed a machine capable of performing the following operation multiple times:
Select a positive integer ;
Identify the first tree (the one with the smallest index) that currently has at least coins;
Remove coins from that tree.
According to the coin tree care manual, after harvesting, each tree must retain at least one coin to ensure it produces coins the following year.
Cossack Vus wants to know the maximum number of coins the machine can collect through a series of operations, while ensuring that each tree is left with at least one coin.
Note that the value of can vary with each operation.
The first line contains a single integer (1 \leq n \leq 10^6) — the number of trees in the Field of Wonders.
The second line contains integers a_1, a_2, \ldots, a_n (1 \leq a_i \leq 10^9) — the initial number of coins on each tree.
Output a single integer — the maximum number of coins the machine can collect after performing a sequence of operations, ensuring that at least one coin remains on each tree.
Example 1
Example 2
In the second example, it is impossible to choose a that allows for the collection of at least one coin while leaving coins on each tree.
( points): n=2;
( points): n=3;
( points): a_i \leq 2;
( points): a_i \leq 3;
( points): 10 \leq a_i;
( points): a_i, n \leq 1\,000;
( points): no additional constraints.