Cossack Vus and the Field of Wonders

Cossack Vus recently discovered a fascinating place called the Field of Wonders, where trees that grow coins can be found. He decided to plant $n$ 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 $i$-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 $k$;

• Identify the first tree (the one with the smallest index) that currently has at least $k$ coins;

• Remove $k$ 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 $k$ can vary with each operation.

Input

The first line contains a single integer $n$ ($1\le n\le 10^6$) — the number of trees in the Field of Wonders.

The second line contains $n$ integers $a_1,a_2,\dots ,a_n$ ($1\le a_i\le 10^9$) — the initial number of coins on each tree.

Output

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.

Examples

Note

In the second example, it is impossible to choose a $k$ that allows for the collection of at least one coin while leaving coins on each tree.

Scoring

1. ($4$ points): $n=2$;

2. ($8$ points): $n=3$;

3. ($7$ points): $a_i\le 2$;

4. ($13$ points): $a_i\le 3$;

5. ($7$ points): $10\le a_i$;

6. ($19$ points): $a_i,n\le 1000$;

7. ($42$ points): no additional constraints.