Problem Description

There are n bowls, numbered from 1 to n. Initially, bowl i contains m_i marbles. One game step consists of removing one marble from a bowl. When removing a marble from bowl i (i > 1), one marble is added to each of the first i-1 bowls; if a marble is removed from bowl 1, no new marble is added. The game is finished after each bowl is empty.

Your job is to determine how many game steps are needed to finish the game. You may assume that the supply of marbles is sufficient, and each bowl is large enough, so that each possible game step can be executed.

Input

The input contains several test cases. Each test case consists of one line containing one integer n (1 ≤ n ≤ 50), the number of bowls in the game. The following line contains n integers m_i (1 ≤ i ≤ n, 0 ≤ m_i ≤ 1000), where m_i gives the number of marbles in bowl i at the beginning of the game.

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

 

Output

For each test case, print one line with the number of game steps needed to finish the game. You may assume that this number fits into a signed 64-bit integer.

Sample Input

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

Sample Output

3069
129

 

Source

2008水题公开赛（比速度，OJ压力测试）

 

Recommend

lcy   |   We have carefully selected several similar problems for you:  2371 2370 2369 2372 2375 

代码如下：

#include <cstdio>
int main()
{
	int n, i, j;
	__int64 a[56];
	while(scanf("%d",&n) && n)
	{
		for(i = 1; i <= n; i++)
		{
			scanf("%I64d",&a[i]);
		}
		__int64 ans = 0;
		for(i = n; i > 0; i--)
		{
			ans+=a[i];
			for(j = i-1; j > 0; j--)
			{
				a[j]+=a[i];
			}
		}
		printf("%I64d\n",ans);
	}
	return 0;
}