Milk Exchange

문제

Farmer John's $NN$ $(1\le N\le 5\cdot {10}^5)(1\; \backslash leq\; N\; \backslash leq\; 5\; \backslash cdot\; 10^5)$ cows are lined up in a circle. The $ii$th cow has a bucket with integer capacity $a_{i}a\_i$ $(1\le a_i\le {10}^9)(1\; \backslash leq\; a\_i\; \backslash leq\; 10^9)$ liters. All buckets are initially full.

Every minute, cow $ii$ will pass all the milk in their bucket to cow $i+1i+1$ for , with cow $NN$ passing its milk to cow $11$. All exchanges happen simultaneously (i.e., if a cow has a full bucket but gives away $xx$ liters of milk and also receives $xx$ liters, her milk is preserved). If a cow's total milk ever ends up exceeding $a_{i}a\_i$, then the excess milk will be lost.

After each of $1,2,\dots ,N1,\; 2,\; \backslash dots,\; N$ minutes, how much total milk is left among all cows?

입력

The first line contains $NN$.

The next line contains integers $a_1,a_2,\mathrm{.}\mathrm{.}\mathrm{.},a_{N}a\_1,a\_2,...,a\_N$.

출력

Output $NN$ lines, where the $ii$-th line is the total milk left among all cows after $ii$ minutes.

6
2 2 2 1 2 1

8
7
6
6
6
6

8
3 8 6 4 8 3 8 1

25
20
17
14
12
10
8
8

10
9 9 10 10 6 8 2 1000000000 1000000000 1000000000

2000000053
1000000054
56
49
42
35
28
24
20
20