该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

避其锋芒，权且忍让。千载一时，鼎足而立！

作为一名 $\text{ACMer}$，大量的训练是必不可少的。著名的算法竞赛训练网站 secrofedoC 上提供了大量的练习题，同时还会定期举办比赛，以检验选手的学习成果。

小L 希望在 secrofedoC 接下来即将举行的 $n$ 场比赛中取得一个好的成绩。他事先预测出了自己在这 $n$ 场比赛中将会取得的分数：在第 $i$ 场比赛中，他将会获得 $a_i$ 分（注意 $a_i$ 可以为负）。他的总分是所有他参加的比赛的分数之和。不过，并不是每场比赛都必须参加。

小L 发现，他在某些场次可能发挥得不好，从而影响他的整体成绩。因此，他决定沉淀一段时间，静心训练。具体来说，他可以选择一个正整数 $k$ ，跳过所有场次编号不大于 $k$ 的比赛，这些比赛不会影响他的总分；然后，他从编号为 $k+1$ 的比赛开始，依次参与这些比赛并获取对应的分数。

然而，作为大学生，小L 当然不能整天泡在电脑桌前；由于学业的压力，他并不确定自己能打多少比赛。所以他拜托你帮他算出：对于 $[1,n]$ 内的每个正整数 $i$ ，如果他只能参加前 $i$ 场比赛，他最多能获得多少分数。

输入格式

输入共两行。第一行包括一个正整数 $n$ $(1\leq n\leq 2\times 10^5)$ ，表示总共有多少场比赛。

第二行 $n$ 个整数 $a_1,a_2\dots a_n$ $(-10^9 \leq a_i \leq 10^9)$ ，其中第 $i$ 个数表示 小L 参与第 $i$ 场比赛能获得的分数。

输出格式

输出一行 $n$ 个数，其中第 $i$ 个数表示 小L 在只能参与前 $i$ 场比赛的情况下最多能获得的分数。

7
2 -4 -1 2 3 -2 5

2 0 0 2 5 3 8

提示

以下是 小L 对于 $[1,n]$ 之间每个 $i$ 的最优策略：

• $i=1$ ：前 $1$ 场比赛的分数为 $[2]$ 。他的最优策略是不放弃任何比赛，获得 $2$ 分。

• $i=2$ ：前 $2$ 场比赛的分数为 $[2,-4]$ 。他的最优策略是放弃前 $2$ 场比赛，获得 $0$ 分。

• $i=3$ ：前 $3$ 场比赛的分数为 $[2,-4,-1]$ 。他的最优策略是放弃前 $3$ 场比赛，获得 $0$ 分。

• $i=4$ ：前 $4$ 场比赛的分数为 $[2,-4,-1,2]$ 。他的最优策略是放弃前 $3$ 场比赛，获得 $2$ 分。

• $i=5$ ：前 $5$ 场比赛的分数为 $[2,-4,-1,2,3]$ 。他的最优策略是放弃前 $3$ 场比赛，获得 $5$ 分。

• $i=6$ ：前 $6$ 场比赛的分数为 $[2,-4,-1,2,3,-2]$ 。他的最优策略是放弃前 $3$ 场比赛，获得 $3$ 分。

• $i=7$ ：前 $7$ 场比赛的分数为 $[2,-4,-1,2,3,-2,5]$ 。他的最优策略是放弃前 $3$ 场比赛，获得 $8$ 分。

可以证明，不存在能够获得更高分数的方案。