题目描述

有 $n$ 个小球，第 $i$ 个小球上写着一个数字 $a_i$ 代表它的分数。对于一个固定的参数 $m$（$1\leq m\leq n$）可以进行如下游戏：Dave 初始分数为 $0$，把第 $1\sim (m-1)$ 个小球先放进一个空桶（如果 $m=1$，则桶初始为空），此后依次把第 $m,m+1,\cdots,n$ 个小球放进桶中，每次把球放进桶后，Dave 从中任选一个球拿出来，将其分数加到自己的分数上，然后把这个球从桶中移走。

Dave 觉得只玩一次游戏太没意思了，于是想对 $m=1,2,\cdots,n$ 都进行一次游戏，请你分别求出 Dave 在每次游戏中能得到的最大分数。

输入格式

第一行一个整数 $n$。

第二行 $n$ 个整数 $a_1,\cdots,a_n$。

输出格式

一行 $n$ 个整数，第 $i$ 个整数表示 $m=i$ 时的最大分数。

5
114 1 1 4 5

125 124 123 119 114

样例解释 1

当 m=4，初始桶中有 1,1,114，放入第 4 个球之后桶中有 1,1,4,114，拿走 114； 再放入第 5 个球后桶中有 1,1,5，拿走 5，于是最多拿走 114+5=119，所以输出的第四个数是 119。

5
112270760 370279431 952521231 607482856 827094551

2869648829 2757378069 2387098638 1779615782 952521231

数据范围

对于 $30\%$ 的数据，$1\leq n\leq 5$。

对于 $60\%$ 的数据，$1\leq n\leq 1000$。

对于 $100\%$ 的数据，$1\leq n\leq 2\times 10^5$，$1\leq a_i\leq 10^9$。