{"raw_statement":[{"iden":"problem statement","content":"For a sequence $a = (a_1, a_2, a_3, \\dots, a_k)$, let $f(a)$ be the sum of its elements after the following is done:\n\n*   For each $i = 1, 2, 3, \\dots, k$, in this order, do the following operation:  \n    add the current maximum value of an element in $a$ to $a_i$.\n\nYou are given a sequence of length $N$: $A = (A_1, A_2, A_3, \\dots, A_N)$.  \nFor each integer $k$ between $1$ and $N$ (inclusive), find $f(a)$ when $a = (A_1, A_2, A_3, \\dots, A_k)$."},{"iden":"constraints","content":"*   $1 \\le N \\le 2 \\times 10^5$\n*   $1 \\le A_i \\le 10^7$\n*   All values in input are integers."},{"iden":"input","content":"Input is given from Standard Input in the following format:\n\n$N$\n$A_1$ $A_2$ $A_3$ $\\dots$ $A_N$"},{"iden":"sample input 1","content":"3\n1 2 3"},{"iden":"sample output 1","content":"2\n8\n19\n\nFor example, when $a = (A_1, A_2, A_3)$, $f(a)$ is computed as follows:\n\n*   First, for $i = 1$, add to $a_1$ the current maximum value of $a$, which is $3$, making $a = (4, 2, 3)$.\n*   Next, for $i = 2$, add to $a_2$ the current maximum value of $a$, which is $4$, making $a = (4, 6, 3)$.\n*   Finally, for $i = 3$, add to $a_3$ the current maximum value of $a$, which is $6$, making $a = (4, 6, 9)$.\n*   $f(a)$ is the sum of the elements of $a$ now, which is $19$."}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}