Problem 2. Milk Exchange

USACO 2024 February Contest, Gold

Farmer John 的 $N$（$1 \leq N \leq 5 \cdot 10^5$）头奶牛排成一圈。第 $i$ 头奶牛有一个容量为整数 $a_i$（$1 \leq a_i \leq 10^9$）升的桶。所有桶初始时都是满的。

每一分钟，对于 $1\le i<N$，奶牛 $i$ 会将其桶中所有牛奶传递给奶牛 $i+1$，奶牛 $N$ 将其牛奶传递给奶牛 $1$。所有交换同时发生（即，如果一头奶牛的桶是满的，送出 $x$ 升牛奶同时收到 $x$ 升，则她的牛奶量保持不变）。如果此时一头奶牛的牛奶量超过 $a_i$，则多余的牛奶会损失。

在 $1, 2, \dots, N$ 的每一分钟后，所有奶牛总共还余下多少牛奶？

输入格式（从终端 / 标准输入读入）：

输入的第一行包含 $N$。

第二行包含 $a_1,a_2,...,a_N$。

输出格式（输出至终端 / 标准输出）：

输出 $N$ 行，其中第 $i$ 行包含 $i$ 分钟后所有奶牛总共余下的牛奶量。

输入样例：

6
2 2 2 1 2 1

输出样例：

8
7
6
6
6
6

最初，每个桶中的牛奶量为 $[2, 2, 2, 1, 2, 1]$。

• $1$ 分钟后，每个桶中的牛奶量为 $[1, 2, 2, 1, 1, 1]$，因此总牛奶量为 $8$。
• $2$ 分钟后，每个桶中的牛奶量为 $[1, 1, 2, 1, 1, 1]$，因此总牛奶量为 $7$。
• $3$ 分钟后，每个桶中的牛奶量为 $[1, 1, 1, 1, 1, 1]$，因此总牛奶量为 $6$。
• $4$ 分钟后，每个桶中的牛奶量为 $[1, 1, 1, 1, 1, 1]$，因此总牛奶量为 $6$。
• $5$ 分钟后，每个桶中的牛奶量为 $[1, 1, 1, 1, 1, 1]$，因此总牛奶量为 $6$。
• $6$ 分钟后，每个桶中的牛奶量为 $[1, 1, 1, 1, 1, 1]$，因此总牛奶量为 $6$。

输入样例：

8
3 8 6 4 8 3 8 1

输出样例：

25
20
17
14
12
10
8
8

$1$ 分钟后，每个桶中的牛奶量为 $[1, 3, 6, 4, 4, 3, 3, 1]$，因此总牛奶量为 $25$。

输入样例：

10
9 9 10 10 6 8 2 1000000000 1000000000 1000000000

输出样例：

2000000053
1000000054
56
49
42
35
28
24
20
20

测试点性质： 测试点 4-5：$N \le 2000$。测试点 6-8：$a_i \le 2$。测试点 9-13：所有 $a_i$ 在范围 $[1,10^9]$ 内均匀随机生成。测试点 14-23：没有额外限制。

供题：Chongtian Ma，Alex Liang，Patrick Deng