题目描述

有 nn 个小球，第 ii 个小球上写着一个数字 aiai​ 代表它的分数。对于一个固定的参数 mm（1≤m≤n1≤m≤n）可以进行如下游戏：Dave 初始分数为 00，把第 1∼(m−1)1∼(m−1) 个小球先放进一个空桶（如果 m=1m=1，则桶初始为空），此后依次把第 m,m+1,⋯ ,nm,m+1,⋯,n 个小球放进桶中，每次把球放进桶后，Dave 从中任选一个球拿出来，将其分数加到自己的分数上，然后把这个球从桶中移走。

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

输入格式

第一行一个整数 nn。

第二行 nn 个整数 a1,⋯ ,ana1​,⋯,an​。

输出格式

一行 nn 个整数，第 ii 个整数表示 m=im=i 时的最大分数。

数据范围

对于 30%30% 的数据，1≤n≤51≤n≤5。

对于 60%60% 的数据，1≤n≤10001≤n≤1000。

对于 100%100% 的数据，1≤n≤2×1051≤n≤2×105，1≤ai≤1091≤ai​≤109。

样例数据

输入:

5
114 1 1 4 5

输出:

125 124 123 119 114

说明:

当 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

详见代码:

#include <bits/stdc++.h>
using namespace std;
int n;
long long ans;
int a[200005];
int main() {
    cin >> n;
    for(int i = 1; i <= n; i++) 
    {
        cin >> a[i];
        ans += a[i];
    }
    sort(a + 1, a + n + 1);
    for(int i = 1; i <= n; i++) 
    {
        cout << ans << " ";
        ans -= a[i];
    }
    return 0;
}