{"raw_statement":[{"iden":"problem statement","content":"Given is a sequence of integers $A = (A_1, \\ldots, A_N)$.\nConsider a pair of sequences of integers $B = (B_1, \\ldots, B_N)$ and $C = (C_1, \\ldots, C_N)$ that satisfies the following conditions:\n\n*   $A_i = B_i + C_i$ holds for each $1\\leq i\\leq N$;\n*   $B$ is non-decreasing, that is, $B_i\\leq B_{i+1}$ holds for each $1\\leq i\\leq N-1$;\n*   $C$ is non-increasing, that is, $C_i\\geq C_{i+1}$ holds for each $1\\leq i\\leq N-1$.\n\nFind the minimum possible value of $\\sum_{i=1}^N \\bigl(\\lvert B_i\\rvert + \\lvert C_i\\rvert\\bigr)$."},{"iden":"constraints","content":"*   $1\\leq N\\leq 2\\times 10^5$\n*   $-10^8\\leq A_i\\leq 10^8$"},{"iden":"input","content":"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":"3\n1 -2 3"},{"iden":"sample output 1","content":"10\n\nOne pair of sequences $B = (B_1, \\ldots, B_N)$ and $C = (C_1, \\ldots, C_N)$ that yields the minimum value is:\n\n*   $B = (0, 0, 5)$,\n*   $C = (1, -2, -2)$.\n\nHere we have $\\sum_{i=1}^N \\bigl(\\lvert B_i\\rvert + \\lvert C_i\\rvert\\bigr) = (0+1) + (0+2) + (5+2) = 10$."},{"iden":"sample input 2","content":"4\n5 4 3 5"},{"iden":"sample output 2","content":"17\n\nOne pair of sequences $B$ and $C$ that yields the minimum value is:\n\n*   $B = (0, 1, 2, 4)$,\n*   $C = (5, 3, 1, 1)$."},{"iden":"sample input 3","content":"1\n-10"},{"iden":"sample output 3","content":"10\n\nOne pair of sequences $B$ and $C$ that yields the minimum value is:\n\n*   $B = (-3)$,\n*   $C = (-7)$."}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}