{"raw_statement":[{"iden":"problem statement","content":"You are given an integer sequence of length $N$: $(A_1, A_2, \\ldots, A_N)$. There is also a sequence $S$, which is initially empty.\nFor each $i = 1, 2, \\ldots, N$ in this order, you perform exactly one of the following two operations:\n\n*   Append $A_i$ as an element to the end of $S$.\n*   Delete the last element of $S$. You cannot choose this operation if $S$ is empty.\n\nPrint the maximum possible value of the sum of the elements of $S$ after all operations."},{"iden":"constraints","content":"*   $1 \\leq N \\leq 2 \\times 10^5$\n*   $-10^9 \\leq A_i \\leq 10^9$\n*   All input values are integers."},{"iden":"input","content":"The input is given from Standard Input in the following format:\n\n$N$\n$A_1$ $A_2$ $\\ldots$ $A_N$"},{"iden":"sample input 1","content":"6\n3 -1 -4 5 -9 2"},{"iden":"sample output 1","content":"8\n\nStarting from the initial state where $S$ is an empty sequence, consider the following operations:\n\n*   For $i = 1$, append $A_1 = 3$ to the end of $S$. Now, $S = (3)$.\n*   For $i = 2$, append $A_2 = -1$ to the end of $S$. Now, $S = (3, -1)$.\n*   For $i = 3$, delete the last element of $S$. Now, $S = (3)$.\n*   For $i = 4$, append $A_4 = 5$ to the end of $S$. Now, $S = (3, 5)$.\n*   For $i = 5$, append $A_5 = -9$ to the end of $S$. Now, $S = (3, 5, -9)$.\n*   For $i = 6$, delete the last element of $S$. Now, $S = (3, 5)$.\n\nHere, the sum of the elements of $S$ after all operations is $3 + 5 = 8$, which is the maximum possible value."},{"iden":"sample input 2","content":"1\n-1"},{"iden":"sample output 2","content":"\\-1\n\nNote that if $S$ is empty, you must choose to append an element."},{"iden":"sample input 3","content":"20\n-14 74 -48 38 -51 43 5 37 -39 -29 80 -44 -55 59 17 89 -37 -68 38 -16"},{"iden":"sample output 3","content":"369"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}