A Game with Marbles

Time limit1sMemory limit128 MB

Summary

Each move takes one marble from a bowl and, if it is not bowl 1, adds one marble to every lower-numbered bowl; count the total moves until all bowls are empty.

Level: Medium5 of 10
Topics: Dynamic programming, Math, Combinatorics
Solved: No attempts yet

Problem

There are $n$ bowls numbered from $1$ to $n$ . Initially, bowl $i$ contains $m_i$ marbles.

One move consists of removing a single marble from some bowl. When a marble is removed from bowl $i$ with $i > 1$ , one marble is added to each of the bowls $1, 2, \dots, i-1$ . Removing a marble from bowl $1$ adds no new marbles anywhere. The game ends once every bowl is empty.

Determine how many moves are needed to finish the game. You may assume the supply of marbles is unlimited and every bowl is large enough, so that every possible move can be performed.

Input

The input contains several test cases. Each test case begins with a line containing one integer $n$ ( $1 \le n \le 50$ ), the number of bowls. The next line contains $n$ integers $m_1, m_2, \dots, m_n$ ( $0 \le m_i \le 1000$ ), where $m_i$ is the number of marbles in bowl $i$ at the start.

The last test case is followed by a line containing a single $0$ .

Output

For each test case, print a single line with the number of moves needed to finish the game. This number is guaranteed to fit in a signed 64-bit integer.

Examples5

Example 1

Input

10
3 3 3 3 3 3 3 3 3 3
5
1 2 3 4 5
0

Expected output

3069
129

Example 2
Input
```
1
0
0
```
Expected output
```
0
```
Example 3
Input
```
1
1000
0
```
Expected output
```
1000
```
Example 4
Input
```
2
5 7
0
```
Expected output
```
19
```
Example 5
Input
```
1
7
3
1 1 1
2
1000 1000
0
```
Expected output
```
7
7
3000
```