201233: [AtCoder]ARC123 D - Inc, Dec - Decomposition

Memory Limit:1024 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

Score : $700$ points

Problem Statement

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:

  • $A_i = B_i + C_i$ holds for each $1\leq i\leq N$;
  • $B$ is non-decreasing, that is, $B_i\leq B_{i+1}$ holds for each $1\leq i\leq N-1$;
  • $C$ is non-increasing, that is, $C_i\geq C_{i+1}$ holds for each $1\leq i\leq N-1$.

Find the minimum possible value of $\sum_{i=1}^N \bigl(\lvert B_i\rvert + \lvert C_i\rvert\bigr)$.

Constraints

  • $1\leq N\leq 2\times 10^5$
  • $-10^8\leq A_i\leq 10^8$

Input

Input is given from Standard Input in the following format:

$N$
$A_1$ $A_2$ $\ldots$ $A_N$

Output

Print the answer.


Sample Input 1

3
1 -2 3

Sample Output 1

10

One pair of sequences $B = (B_1, \ldots, B_N)$ and $C = (C_1, \ldots, C_N)$ that yields the minimum value is:

  • $B = (0, 0, 5)$,
  • $C = (1, -2, -2)$.

Here we have $\sum_{i=1}^N \bigl(\lvert B_i\rvert + \lvert C_i\rvert\bigr) = (0+1) + (0+2) + (5+2) = 10$.


Sample Input 2

4
5 4 3 5

Sample Output 2

17

One pair of sequences $B$ and $C$ that yields the minimum value is:

  • $B = (0, 1, 2, 4)$,
  • $C = (5, 3, 1, 1)$.

Sample Input 3

1
-10

Sample Output 3

10

One pair of sequences $B$ and $C$ that yields the minimum value is:

  • $B = (-3)$,
  • $C = (-7)$.

Input

题意翻译

给出长为 $n$ 的序列 $a$,构造长为 $n$ 的序列 $b,c$,要求: - $b$ 非严格递增。 - $c$ 非严格递减。 - $b_i+c_i=a_i$ 。 最小化 $\sum_{i=1}^n |b_i|+|c_i|$。

加入题单

上一题 下一题 算法标签: