分数: 100 点
问题陈述
的最小公倍数 Shobon 提出了以下问题:
Marunomi
给你一个正整数序列 W = (w_1, w_2, \dots, w_N).
有 N 个活的史莱姆,名字叫 Slime 1, 2, \dots, N.
最初,Slime 的重量 i (1 \leq i \leq N) 是 w_i,它的胜利次数是 0.你可以对史莱姆执行以下操作零次或多次:
- 选择两个活的史莱姆,比如史莱姆 i 和史莱姆 j (i \neq j).
- 记下史莱姆的当前重量 i be W_i 和史莱姆的 j be W_j.
- If W_i \gt W_j胜利次数 i 增加 1,它的重量变为 W_i + W_j,而史莱姆 j 去世。
- 如果不满足此条件,则不会发生任何事情。
对于每个 i = 1, 2, \dots, N,让 S_i 是史莱姆 i 通过你的行动可以达到的最大胜利次数。
计算值 S_1 + S_2 + \dots + S_N.
但是,由于这个问题类似于 ARC189 D - 高桥是史莱姆,noya2 将其修改如下:
所有前缀的 Marunami
给你一个正整数序列 A = (a_1, a_2, \dots, a_M).
对于每个 i = 1, 2, \dots, M,当计算 Marunomi 问题的答案时 W = (a_1, a_2, \dots, a_i).
解决这个问题。
约束
- 所有输入值均为整数。
- 1 \leq M \leq 2 \times 10^5
- 1 \leq a_i \leq 10^9\ (1 \leq i \leq M)
输入
输入按以下格式给出:
M a_1 a_2 \cdots a_M
输出
输出 M 行。的 i- 第行 (1 \leq i \leq M)应包含 Marunomi 问题的答案 W = (a_1, a_2, \dots, a_i).
示例输入 1
5 1 2 3 5 20
示例输出 1
0 1 3 7 11
示例输入 2
3 1 1 1
示例输出 2
0 0 0
示例输入 3
10 17 3467 115 716 9070 32 12251 237 549 17
示例输出 3
0 1 3 6 10 15 22 29 38 46