AT_2_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 类似，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 自动生成