← 返回题目列表

AtCoder · ttpc2024_2_o

O. Marunomi 适用于所有前缀

中文机器翻译题面 查看原题

分数: 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