AT_ttpc2024_2_o Marunomi for All Prefixes

Shobon 想到了一个有趣的问题。 > #### 史莱姆吞噬 > > 现有一个正整数序列 $ W = (w_1, w_2, \dots, w_N) $。 > > 有 $ N $ 只史莱姆，编号分别是 $ 1, 2, \dots, N $。最初，每只史莱姆 $ i $（$ 1 \leq i \leq N $）的重量是 $ w_i $，胜利次数是 $ 0 $。 > > 你可以对这些史莱姆执行以下操作任意次： > > - 选择任意两个编号不同且活着的史莱姆，分别是史莱姆 $ i $ 和史莱姆 $ j\ (i \neq j)$。 > - 设史莱姆 $ i $ 的重量为 $ W_i $，史莱姆 $ j $ 的重量为 $ W_j $。 > - 如果 $ W_i > W_j $，则史莱姆 $ i $ 的胜利次数加 $ 1 $，其重量变为 $ W_i + W_j $，同时史莱姆 $ j $ 消亡。 > - 否则，就什么也不做。 > >  > > 对于每个 $ i = 1, 2, \dots, N $，假设我们尽可能增加史莱姆 $ i $ 的胜利次数，将其最大化，记为 $ S_i $。 > 求 $ S_1 + S_2 + \dots + S_N $ 的总和。 由于该问题与 [ARC189 D - Takahashi is Slime](https://atcoder.jp/contests/arc189/tasks/arc189_d) 类似，noya2 将其变为： > #### 前缀史莱姆吞噬 > > 给定一个正整数序列 $ A = (a_1, a_2, \dots, a_M) $。 > > 对每个 $ i = 1, 2, \dots, M $，计算当输入序列 $ W = (a_1, a_2, \dots, a_i) $ 时，上述问题的结果。 请解决这个问题。

输入格式如下： > $ M $ $ a_1 $ $ a_2 $ $ \cdots $ $ a_M $

输出 $ M $ 行。对于每个 $ i $（$ 1 \leq i \leq M $），输出第 $ i $ 行，表示当输入 $ 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) $。 **本翻译由 AI 自动生成**