AT_ttpc2024_2_o Marunomi for All Prefixes

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](https://atcoder.jp/contests/arc189/tasks/arc189_d) と似ているため、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) $ を入力したときの答えを求めてください。 この問題を解いてください。

入力は以下の形式で与えられる。 > $ M $ $ a_1 $ $ a_2 $ $ \cdots $ $ a_M $

$ M $ 行出力せよ。 $ i $ 行目 $ (1

### Constraints - 入力はすべて整数 - $ 1 \leq M \leq 2 \times 10^5 $ - $ 1 \leq a_i \leq 10^9\ (1 \leq i \leq M) $