{"raw_statement":[{"iden":"problem statement","content":"There are $N$ dishes arranged in a row in front of Takahashi. The $i$\\-th dish from the left has $A_i$ oranges on it.\nTakahashi will choose a triple of integers $(l, r, x)$ satisfying all of the following conditions:\n\n*   $1\\leq l \\leq r \\leq N$;\n*   $1 \\le x$;\n*   for every integer $i$ between $l$ and $r$ (inclusive), $x \\le A_i$.\n\nHe will then pick up and eat $x$ oranges from each of the $l$\\-th through $r$\\-th dishes from the left.\nAt most how many oranges can he eat by choosing the triple $(l, r, x)$ to maximize this number?"},{"iden":"constraints","content":"*   All values in input are integers.\n*   $1 \\leq N \\leq 10^4$\n*   $1 \\leq A_i \\leq 10^5$"},{"iden":"input","content":"Input is given from Standard Input in the following format:\n\n$N$\n$A_1$ $\\ldots$ $A_N$"},{"iden":"sample input 1","content":"6\n2 4 4 9 4 9"},{"iden":"sample output 1","content":"20\n\nBy choosing $(l,r,x)=(2,6,4)$, he can eat $20$ oranges."},{"iden":"sample input 2","content":"6\n200 4 4 9 4 9"},{"iden":"sample output 2","content":"200\n\nBy choosing $(l,r,x)=(1,1,200)$, he can eat $200$ oranges."}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}