当前没有测试数据。

一、Problem Name

Milk Exchange

二、Problem Description

Farmer John's $N$ ($1\leq N\leq5\cdot10^5$) cows are lined up in a circle. The $i$th cow has a bucket with integer capacity $a_i$ ($1\leq a_i\leq10^9$) liters. All buckets are initially full.

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

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

三、Input Format (input arrives from the terminal / stdin)

1. The first line contains $N$.
2. The next line contains integers $a_1,a_2,\cdots,a_N$.

四、Output Format (print output to the终端 / stdout)

Output $N$ lines, where the $i$th line is the total milk left among all cows after $i$ minutes.

五、Sample Input and Output

Sample Input 1

6
2 2 2 1 2 1

Sample Output 1

8
7
6
6
6
6

Explanation: Initially, the amount of milk in each bucket is $[2,2,2,1,2,1]$. After 1 minute, the amount of milk in each bucket is $[1,2,2,1,1,1]$ so the total amount of milk is 8. After 2 minutes, the amount of milk in each bucket is $[1,1,2,1,1,1]$ so the total amount of milk is 7. And so on.

Sample Input 2

8
3 8 6 4 8 3 8 1

Sample Output 2

25
20
17
14
12
10
8
8

Explanation: After 1 minute, the amount of milk in each bucket is $[1,3,6,4,4,3,3,1]$ so the total amount of milk is 25.

Sample Input 3

10
9 9 10 10 6 8 2 1000000000 1000000000 1000000000

Sample Output 3

2000000053
1000000054
56
49
42
35
28
24
20
20

六、Scoring Rules

1. Inputs 4 - 5: $N\leq2000$.
2. Inputs 6 - 8: $a_i\leq2$.
3. Inputs 9 - 13: All $a_i$ are generated uniformly at random in the range $[1,10^9]$.
4. Inputs 14 - 23: No additional constraints.

Problem credits: Chongtian Ma, Alex Liang, Patrick Deng.