O - Marunomi for All Prefixes Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

Score: 100 points

Problem Statement

Shobon proposed the following problem:

Marunomi

You are given a sequence of positive integers W = (w_1, w_2, \dots, w_N).

There are N living slimes, named Slime 1, 2, \dots, N.
Initially, the weight of Slime i (1 \leq i \leq N) is w_i, and its number of victories is 0.

You can perform the following operation on the slimes zero or more times:

  • Choose two living slimes, say Slime i and Slime j (i \neq j).
    • Let the current weight of Slime i be W_i and that of Slime j be W_j.
    • If W_i \gt W_j, the number of victories of Slime i increases by 1, its weight becomes W_i + W_j, and Slime j dies.
    • If this condition is not satisfied, nothing happens.

For each i = 1, 2, \dots, N, let S_i be the maximum number of victories Slime i can achieve through your actions.
Calculate the value of S_1 + S_2 + \dots + S_N.

However, since this problem is similar to ARC189 D - Takahashi is Slime, noya2 modified it as follows:

Marunomi for All Prefixes

You are given a sequence of positive integers A = (a_1, a_2, \dots, a_M).

For each i = 1, 2, \dots, M, compute the answer to the Marunomi problem when W = (a_1, a_2, \dots, a_i).

Solve this problem.

Constraints

  • All input values are integers.
  • 1 \leq M \leq 2 \times 10^5
  • 1 \leq a_i \leq 10^9\ (1 \leq i \leq M)

Input

The input is given in the following format:

M
a_1 a_2 \cdots a_M

Output

Output M lines. The i-th line (1 \leq i \leq M) should contain the answer to the Marunomi problem for W = (a_1, a_2, \dots, a_i).

Sample Input 1

5
1 2 3 5 20

Sample Output 1

0 1 3 7 11

Sample Input 2

3
1 1 1

Sample Output 2

0 0 0

Sample Input 3

10
17 3467 115 716 9070 32 12251 237 549 17

Sample Output 3

0 1 3 6 10 15 22 29 38 46

配点 : 100 点

問題文

Shobon さんは以下の問題を考えました。

Marunomi

正整数の列 W = (w_1, w_2, \dots, w_N) が与えられます。

N 体の生きているスライムがあり、スライム 1, 2, \dots, N と名付けられています。 最初、スライム i ( 1 \leq i \leq N ) の重さは w_i 、勝利数は 0 です。

これらのスライムに対して、あなたは次の操作を 0 回以上行うことができます。

  • 生きているスライムを 2 体選び、それぞれ、スライム i 、スライム j\ (i \neq j) とする。
    • 現在のスライム i の重さを W_i 、スライム j の重さを W_j とする。
    • W_i \gt W_j を満たすとき、スライム i の勝利数が 1 増加し、重さが W_i + W_j となる。また、スライム j は死亡する。
    • そうでないとき、なにも起こらない。

i=1,2,\dots,N のそれぞれについて、あなたがスライム i の勝利数を最大化するように行動した場合のスライム i の勝利数を S_i とします。
S_1 + S_2 + \dots + S_N の値を求めてください。

しかし、この問題は ARC189 D - Takahashi is Slime と似ているため、noya2 さんは以下のように改題しました。

Marunomi for All Prefixes

正整数の列 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 ≤ i ≤ 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