题目描述
有 n 个小球，第 ii个小球上写着一个数字ai 代表它的分数。对于一个固定的参数 m（1≤m≤n）可以进行如下游戏：Dave 初始分数为 0，把第 1∼(m−1) 个小球先放进一个空桶（如果 m=1，则桶初始为空），此后依次把第 m,m+1,⋯,n 个小球放进桶中，每次把球放进桶后，Dave 从中任选一个球拿出来，将其分数加到自己的分数上，然后把这个球从桶中移走。NJI100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
Dave 觉得只玩一次游戏太没意思了，于是想对 m=1,2,⋯,n 都进行一次游戏，请你分别求出 Dave 在每次游戏中能得到的最大分数。NJI100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
输入格式
第一行一个整数 n。NJI100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
第二行 n 个整数a1,⋯,an。NJI100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
输出格式
一行 n个整数，第 ii个整数表示m=i 时的最大分数。NJI100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
数据范围
对于 30% 的数据，1≤n≤5。NJI100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
对于 60% 的数据，1≤n≤1000。NJI100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
对于 100% 的数据，1≤n≤2×10^5，1≤ai≤10^9。NJI100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
NJI100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
样例数据
输入:NJI100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
5NJI100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
114 1 1 4 5NJI100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
输出:NJI100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
125 124 123 119 114NJI100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
说明:NJI100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
当 m=4，初始桶中有 1,1,114，放入第 4 个球之后桶中有 1,1,4,114，拿走 114；NJI100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
再放入第 5 个球后桶中有 1,1,5，拿走 5，于是最多拿走 114+5=119，所以输出的第四个数是 119。NJI100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
输入:NJI100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
5NJI100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
112270760 370279431 952521231 607482856 827094551NJI100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
输出:NJI100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
2869648829 2757378069 2387098638 1779615782 952521231NJI100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
