Contest Duration: - (local time) (120 minutes) Back to Home
D - Inc, Dec - Decomposition /

Time Limit: 2 sec / Memory Limit: 1024 MB

### 問題文

• 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 = (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 = (0, 1, 2, 4)
• C = (5, 3, 1, 1)

### 入力例 3

1
-10


### 出力例 3

10


• 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


### 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).