题目描述
小 X 决定建立一个团队,但是现在团队里只有小 X 一个人。
在接下的 n 天里,小 X 每天都会招募到一个人,其中加入的第 i 个人的能力值为 vi,小 X 的能力值为 v0=1010100。
为了更好管理整个团队,小 X 需要将团队分成小组。具体的,假设现在已经有 k 个人加入了团队,小 X 希望找到一个序列 0=a0<a1<⋯<am=k+1,使得对于所有 0≤i<m−1,有 $\sum\limits_{j=a_i}^{a_{i+1}-1}v_j>\sum\limits_{j=a_{i+1}}^{a_{i+2}-1}v_j$。
为了让新加入的队员们感受到幸福感,小 X 希望 am 尽可能大,在此基础上 am−1 尽可能大,在此基础上 am−2 尽可能大,以此类推。换句话说,让序列 am,am−1,am−2…a1 的字典序尽可能大。
但是小 X 现在正忙于招募队员,所以他希望你来帮他解决这一问题,你只需要告诉他在 k=1,2…n 的时候, i=0∑m(i×ai) 的值即可。
输入格式
第一行包含一个整数 n。
第二行包含 n 个整数,其中第 i 个数为 vi。
输出格式
输出仅一行,包含 n 个以空格隔开的整数,其中第 i 个数表示 k=i 时的答案。
5
1 3 3 2 4
5 8 19 39 31
提示
【样例 1 解释】
- 对于 k=1,有 m=2,a0=0,a1=1,a2=2,输出 0×0+1×1+2×2=5。
- 对于 k=2,有 m=2,a0=0,a1=2,a2=3,输出 0×0+1×2+2×3=8。
- 对于 k=3,有 m=3,a0=0,a1=1,a2=3,a3=4,输出 0×0+1×1+2×3+3×4=19。
- 对于 k=4,有 m=4,a0=0,a1=1,a2=3,a3=4,a4=5,输出 $0\times 0+1\times 1+2\times 3+3\times 4+4\times 5=39$。
- 对于 k=5,有 m=3,a0=0,a1=3,a2=5,a3=6,输出 0×0+1×3+2×5+3×6=31。
【样例 2】
见选手目录下的 divide/divide2.in
与 divide/divide2.ans
。
样例 2 满足测试点 1∼3 的限制。
【样例 3】
见选手目录下的 divide/divide3.in
与 divide/divide3.ans
。
样例 3 满足测试点 4∼6 的限制。
【样例 4】
见选手目录下的 divide/divide4.in
与 divide/divide4.ans
。
样例 4 满足测试点 7∼10 的限制。
【样例 5】
见选手目录下的 divide/divide5.in
与 divide/divide5.ans
。
样例 5 满足测试点 13∼15 的限制。
【子任务】
对于全部的测试数据,保证 1≤n≤105,1≤vi≤n。
测试点 |
n≤ |
特殊性质 |
1∼3 |
10 |
无 |
4∼6 |
100 |
7∼10 |
5000 |
11,12 |
5×104 |
13∼15 |
105 |
vi 随机生成 |
16∼20 |
无 |