配点: 100 点
問題文
渚的别墅是 N 房间和 N-1 由一条书籍通道组成,每个房间都有 1 从 N ,每个过道都有 编号 1 从 N-1 已分配。i 第一段是一个房间 i 和房间 i+1 双向连接,整数 写入 C_i 。
彩叶酱今天早上在这所房子内的一个房间里醒来。身为忍者的彩羽决定使用忍术逃跑。彩羽酱的情绪用一个整数来表示,这个数字越高,她的忍术成功的可能性就越大。心情的价值是开始 0 和段落 i 当你走过它的时候,你的感觉很好。 C_i ,但该机制将启动,你将无法通过该通道。
起始房间 r 和段落 0 多次访问最喜欢的房间后停在该房间时的最大心情
比方说 X_r 。
所有房间
对于 i 查找 X_i 。
入力
输入是按以下格式从标准输入给出的。
N
C_1
C_2
C_3
...
C_{N-1}
出力
总而言之
请输出 N 行。
i 在线
写在方格 X_i ,即房间
请打印从 i 开始时您的心情最大值。
制約
- 2 \leq N \leq 100000
- -10^9 \leq C_i \leq 10^9
小課題
小課題 1 [15 点]
- N \leq 1000 很满意。 您将获得
- 全部 对于 C_i 是 仅由 0 就是这样。
小課題 2 [30 点]
- 全部 对于 C_i 是 仅由 0 就是这样。
小課題 3 [55 点]
- 没有其他限制。
入力例 1
5 70 10 50 20
出力例 1
150 80 80 130 150
在此示例输入中,别墅的图如下所示:
例如,一个房间 3 开始,
通过路线3 → 2 → 1 前往房间
当我停在 1 时,我感觉
您将得到 10 + 70 = 80 。
没有比这更好的感觉了。
入力例 2
8 70 10 -2000 10000 -2000 50 20
出力例 2
8080 8010 8000 10000 10000 8000 8050 8070
该输入是 1, 2 不满足约束。
入力例 3
7 -45 -45 -45 -45 -45 -45
出力例 3
0 0 0 0 0 0 0