{"raw_statement":[{"iden":"problem statement","content":"Shobon proposed the following problem:\n\n> #### Marunomi\n> \n> You are given a sequence of positive integers $W = (w_1, w_2, \\dots, w_N)$.\n> There are $N$ living slimes, named Slime $1, 2, \\dots, N$.  \n> Initially, the weight of Slime $i$ ($1 \\leq i \\leq N$) is $w_i$, and its number of victories is $0$.\n> You can perform the following operation on the slimes zero or more times:\n> \n> *   Choose two living slimes, say Slime $i$ and Slime $j$ ($i \\neq j$).\n>     *   Let the current weight of Slime $i$ be $W_i$ and that of Slime $j$ be $W_j$.\n>     *   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.\n>     *   If this condition is not satisfied, nothing happens.\n> \n> ![image](https://img.atcoder.jp/ttpc2024_2/38d8d94bdcaac69c081c40d7d91ece34.svg)\n> For each $i = 1, 2, \\dots, N$, let $S_i$ be the maximum number of victories Slime $i$ can achieve through your actions.  \n> Calculate the value of $S_1 + S_2 + \\dots + S_N$.\n\nHowever, since this problem is similar to [ARC189 D - Takahashi is Slime](https://atcoder.jp/contests/arc189/tasks/arc189_d), noya2 modified it as follows:\n\n> #### Marunomi for All Prefixes\n> \n> You are given a sequence of positive integers $A = (a_1, a_2, \\dots, a_M)$.\n> For each $i = 1, 2, \\dots, M$, compute the answer to the Marunomi problem when $W = (a_1, a_2, \\dots, a_i)$.\n\nSolve this problem."},{"iden":"constraints","content":"*   All input values are integers.\n*   $1 \\leq M \\leq 2 \\times 10^5$\n*   $1 \\leq a_i \\leq 10^9\\ (1 \\leq i \\leq M)$"},{"iden":"input","content":"The input is given in the following format:\n\n$M$\n$a_1$ $a_2$ $\\cdots$ $a_M$"},{"iden":"sample input 1","content":"5\n1 2 3 5 20"},{"iden":"sample output 1","content":"0 1 3 7 11"},{"iden":"sample input 2","content":"3\n1 1 1"},{"iden":"sample output 2","content":"0 0 0"},{"iden":"sample input 3","content":"10\n17 3467 115 716 9070 32 12251 237 549 17"},{"iden":"sample output 3","content":"0 1 3 6 10 15 22 29 38 46"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}