{"problem":{"name":"Marunomi for All Prefixes","description":{"content":"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$.   ","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"ttpc2024_2_o"},"statements":[{"statement_type":"Markdown","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.\n\n## Constraints\n\n*   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)$\n\n## Input\n\nThe input is given in the following format:\n\n$M$\n$a_1$ $a_2$ $\\cdots$ $a_M$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"ttpc2024_2_o","tags":[],"sample_group":[["5\n1 2 3 5 20","0 1 3 7 11"],["3\n1 1 1","0 0 0"],["10\n17 3467 115 716 9070 32 12251 237 549 17","0 1 3 6 10 15 22 29 38 46"]],"created_at":"2026-03-03 11:01:14"}}