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.