Problem Description

Farmer John's $N$ ($1 \le N \le 5 \cdot 10^5$) cows are standing in a circle. The $i$-th cow has a bucket with an integer capacity of $a_i$ ($1 \le a_i \le 10^9$) liters. All buckets are initially full.

Every minute, for $1 \le i < N$, cow $i$ passes all the milk in her bucket to cow $i+1$, and cow $N$ passes her milk to cow $1$. All exchanges happen simultaneously (i.e., if a cow's bucket is full, sending $x$ liters of milk while receiving $x$ liters, her milk amount remains unchanged). If at this moment a cow's milk amount exceeds $a_i$, the excess milk is lost.

After $1, 2, \ldots, N$ minutes, how much milk remains in total for all cows?

Input Format

The first line of input contains $N$.

The second line contains $a_1, a_2, \ldots, a_N$.

Output Format

Output $N$ lines, where the $i$-th line contains the total amount of milk remaining for 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

Sample Input #2

8
3 8 6 4 8 3 8 1

Sample Output #2

25
20
17
14
12
10
8
8

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

Notes

Sample Explanation 1

Initially, the milk amounts in the buckets are $[2, 2, 2, 1, 2, 1]$.

• After 1 minute, the milk amounts are $[1, 2, 2, 1, 1, 1]$, so the total milk is $8$.
• After 2 minutes, the milk amounts are $[1, 1, 2, 1, 1, 1]$, so the total milk is $7$.
• After 3 minutes, the milk amounts are $[1, 1, 1, 1, 1, 1]$, so the total milk is $6$.
• After 4 minutes, the milk amounts are $[1, 1, 1, 1, 1, 1]$, so the total milk is $6$.
• After 5 minutes, the milk amounts are $[1, 1, 1, 1, 1, 1]$, so the total milk is $6$.
• After 6 minutes, the milk amounts are $[1, 1, 1, 1, 1, 1]$, so the total milk is $6$.

Sample Explanation 2

After 1 minute, the milk amounts are $[1, 3, 6, 4, 4, 3, 3, 1]$, so the total milk is $25$.

Test Case Properties

• Test cases $4-5$: $N \le 2000$.
• Test cases $6-8$: $a_i \le 2$.
• Test cases $9-13$: All $a_i$ are uniformly randomly generated within the range $[1, 10^9]$.
• Test cases $14-23$: No additional restrictions.

见题面 Input 部分

见题面 Output 部分