#P11822. [湖北省选模拟 2025] 团队分组 / divide

[湖北省选模拟 2025] 团队分组 / divide

题目描述

小 X 决定建立一个团队,但是现在团队里只有小 X 一个人。

在接下的 nn 天里,小 X 每天都会招募到一个人,其中加入的第 ii 个人的能力值为 viv_i,小 X 的能力值为 v0=1010100v_0=10^{10^{100}}

为了更好管理整个团队,小 X 需要将团队分成小组。具体的,假设现在已经有 kk 个人加入了团队,小 X 希望找到一个序列 0=a0<a1<<am=k+10=a_0<a_1<\dots <a_m=k+1,使得对于所有 0i<m10\le 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 希望 ama_m 尽可能大,在此基础上 am1a_{m-1} 尽可能大,在此基础上 am2a_{m-2} 尽可能大,以此类推。换句话说,让序列 am,am1,am2a1a_m,a_{m-1},a_{m-2}\dots a_1 的字典序尽可能大。

但是小 X 现在正忙于招募队员,所以他希望你来帮他解决这一问题,你只需要告诉他在 k=1,2nk=1,2\dots n 的时候, i=0m(i×ai)\sum\limits_{i=0}^m(i\times a_i) 的值即可。

输入格式

第一行包含一个整数 nn

第二行包含 nn 个整数,其中第 ii 个数为 viv_i

输出格式

输出仅一行,包含 nn 个以空格隔开的整数,其中第 ii 个数表示 k=ik=i 时的答案。

5
1 3 3 2 4

5 8 19 39 31

提示

【样例 1 解释】

  • 对于 k=1k=1,有 m=2m=2a0=0,a1=1,a2=2a_0=0,a_1=1,a_2=2,输出 0×0+1×1+2×2=50\times 0+1\times 1+2\times 2=5
  • 对于 k=2k=2,有 m=2m=2a0=0,a1=2,a2=3a_0=0,a_1=2,a_2=3,输出 0×0+1×2+2×3=80\times 0+1\times 2+2\times 3=8
  • 对于 k=3k=3,有 m=3m=3a0=0,a1=1,a2=3,a3=4a_0=0,a_1=1,a_2=3,a_3=4,输出 0×0+1×1+2×3+3×4=190\times 0+1\times 1+2\times 3+3\times 4=19
  • 对于 k=4k=4,有 m=4m=4a0=0,a1=1,a2=3,a3=4,a4=5a_0=0,a_1=1,a_2=3,a_3=4,a_4=5,输出 $0\times 0+1\times 1+2\times 3+3\times 4+4\times 5=39$。
  • 对于 k=5k=5,有 m=3m=3a0=0,a1=3,a2=5,a3=6a_0=0,a_1=3,a_2=5,a_3=6,输出 0×0+1×3+2×5+3×6=310\times 0+1\times 3+2\times 5+3\times 6=31

【样例 2】

见选手目录下的 divide/divide2.individe/divide2.ans

样例 22 满足测试点 131\sim 3 的限制。

【样例 3】

见选手目录下的 divide/divide3.individe/divide3.ans

样例 33 满足测试点 464\sim 6 的限制。

【样例 4】

见选手目录下的 divide/divide4.individe/divide4.ans

样例 44 满足测试点 7107\sim 10 的限制。

【样例 5】

见选手目录下的 divide/divide5.individe/divide5.ans

样例 55 满足测试点 131513\sim 15 的限制。

【子任务】

对于全部的测试数据,保证 1n1051\le n\le 10^51vin1\le v_i\le n

测试点 nn \le 特殊性质
131\sim 3 1010
464\sim 6 100100
7107\sim 10 50005000
11,1211,12 5×1045\times 10^4
131513\sim 15 10510^5 viv_i 随机生成
162016\sim 20