{"problem":{"name":"Inc, Dec - Decomposition","description":{"content":"Given is a sequence of integers $A = (A_1, \\ldots, A_N)$. Consider a pair of sequences of integers $B = (B_1, \\ldots, B_N)$ and $C = (C_1, \\ldots, C_N)$ that satisfies the following conditions: *   $","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"arc123_d"},"statements":[{"statement_type":"Markdown","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)$.\n\n## Constraints\n\n*   $1\\leq N\\leq 2\\times 10^5$\n*   $-10^8\\leq A_i\\leq 10^8$\n\n## Input\n\nInput is given from Standard Input in the following format:\n\n$N$\n$A_1$ $A_2$ $\\ldots$ $A_N$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"arc123_d","tags":[],"sample_group":[["3\n1 -2 3","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$."],["4\n5 4 3 5","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)$."],["1\n-10","10\n\nOne pair of sequences $B$ and $C$ that yields the minimum value is:\n\n*   $B = (-3)$,\n*   $C = (-7)$."]],"created_at":"2026-03-03 11:01:14"}}