续航

时间限制：$2.0\text{ s}$

空间限制：$256\text{ MiB}$

题目描述

一条环形巡检线路被分为顺时针排列的 $n$ 个路段。无人巡检车在每个路段上会消耗电能，也可能在路段末端经过充电导轨获得补给。将车辆完成第 $i$ 段路后的净电量变化记为整数 $a_i$：$a_i<0$ 表示净消耗，$a_i>0$ 表示净补充。

管理中心准备在每个路段起点都保留一个可能的发车位置，因此需要分别计算从不同位置启动时应预充的最少电量。

若选择在第 $s$ 段路之前出发，巡检车依次经过第 $s,s+1,\ldots,n,1,\ldots,s-1$ 段路，恰好行驶一圈后停止。出发前可以向电池中预充任意非负整数单位的电量。

每完成一段路，先将对应的 $a_i$ 加到当前电量上。任何一段路结束后，电量都不能为负；最终回到出发处时可以剩余电量，不要求恰好用完。

对每个 $1\le s\le n$，求从第 $s$ 段路之前出发并完成一圈所需的最小初始电量。各起点的计算相互独立。

输入格式

第一行一个正整数 $n$，表示环形线路的路段数。

第二行 $n$ 个整数 $a_1,a_2,\ldots,a_n$，表示经过各段路后的电量变化。

输出格式

输出一行 $n$ 个非负整数，第 $s$ 个数表示从第 $s$ 段路之前出发所需的最小初始电量。

输入样例 1

4
2 -5 4 -1

输出样例 1

3 5 0 4

输入样例 2

5
-3 1 1 1 1

输出样例 2

3 0 0 1 2

输入样例 3

见附件 sample/charge3.in

输出样例 3

见附件 sample/charge3.out

数据范围

对于所有测试点，保证 $1\le n\le 10^6$，$-10^{12}\le a_i\le 10^{12}$。

每个测试点单独计分。