/ 
実行時間制限: 2 sec / メモリ制限: 1024 MB
配点 : 700 点
問題文
整数列 A = (A_1, \ldots, A_N) が与えられます。
整数列 B = (B_1, \ldots, B_N) および C = (C_1, \ldots, C_N) の組であって、以下の条件を満たすものを考えます：
- 1\leq i\leq N に対して A_i = B_i + C_i が成り立つ。
- B は広義単調増加である。つまり 1\leq i\leq N-1 に対して B_i\leq B_{i+1} が成り立つ。
- C は広義単調減少である。つまり 1\leq i\leq N-1 に対して C_i\geq C_{i+1} が成り立つ。
\sum_{i=1}^N \bigl(\lvert B_i\rvert + \lvert C_i\rvert\bigr) としてありうる最小値を求めてください。
制約
- 1\leq N\leq 2\times 10^5
- -10^8\leq A_i\leq 10^8
入力
入力は以下の形式で標準入力から与えられます。
N A_1 A_2 \ldots A_N
出力
答えを出力してください。
入力例 1
3 1 -2 3
出力例 1
10
最小値を与える整数列 B, C として、例えば次があります：
- B = (0, 0, 5)
- C = (1, -2, -2)
\sum_{i=1}^N \bigl(\lvert B_i\rvert + \lvert C_i\rvert\bigr) = (0+1) + (0+2) + (5+2) = 10 となっています。
入力例 2
4 5 4 3 5
出力例 2
17
最小値を与える整数列 B, C として、例えば次があります：
- B = (0, 1, 2, 4)
- C = (5, 3, 1, 1)
入力例 3
1 -10
出力例 3
10
最小値を与える整数列 B, C として、例えば次があります：
- B = (-3)
- C = (-7)
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).