题目描述

小张同学在一次意外中穿越到了倚天屠龙记的武侠世界，未来能够尽快回到自己的世界，小张在尝试了多次跳崖之后终于找到了藏有乾坤大挪移心法的山洞，乾坤大挪移非常厉害可以帮助小张穿越回来继续接受九年义务教育，小张开心极了 不过在修炼过程中又又又（咦为什么说又呢？）遇到了一些问题，同学们一起帮小张看一下吧！

修炼心法到大圆满需要将$N$（$1\le N \le 5\cdot 10^5$）个穴位排成一个圈，第 $i$ 个穴位所承载的功力为$a_i$（$1\le a_i\le 10^9$），所有穴位初始时候功力都是满的！

修炼过程中，每一分钟，对于 $1\le i<N$，穴位 $i$ 会将其穴位中所有功力传递给穴位$i+1$，穴位 $N$ 将其功力传递给穴位 $1$。所有交换同时发生（即，如果一个穴位是满的，送出 $x$ 功力同时收到 $x$ ，则这个穴位的功力不变）。如果此时一个穴位的功力超过 $a_i$，则多余的牛奶会损失。

在 $1,2,\ldots,N$ 的每一分钟后，所有穴位总共还余下多少功力？

输入格式

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

第二行包含 $a_1,a_2,\ldots,a_N$。

输出格式

输出 $N$ 行，其中第 $i$ 行包含 $i$ 分钟后所有穴位余下的功力数量

输入输出样例 #1

输入 #1

6
2 2 2 1 2 1

输出 #1

8
7
6
6
6
6

输入输出样例 #2

输入 #2

8
3 8 6 4 8 3 8 1

输出 #2

25
20
17
14
12
10
8
8

输入输出样例 #3

输入 #3

10
9 9 10 10 6 8 2 1000000000 1000000000 1000000000

输出 #3

2000000053
1000000054
56
49
42
35
28
24
20
20

说明/提示

样例解释 1

最初，每个穴位中功力为 $[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$。

样例解释 2

$1$ 分钟后，每个穴位中功力为 $[1,3,6,4,4,3,3,1]$，因此总功力为 $25$。

测试点性质

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