Problem Statement

There are cookies at $N$ positions on a number line. The coordinate of the $i$-th cookie is $A_i$.

Takahashi is initially at coordinate $0$ on the number line, and repeats the following action until he has picked up all $N$ cookies.

• Action: Move to the coordinate of the nearest cookie from his current position (if there are multiple such cookies, the one with the smallest coordinate), and pick up that cookie.

Find the total distance Takahashi travels until he picks up all the cookies.

Input

The input is given from Standard Input in the following format:

• $N$
• $A_1$ $\dots$ $A_N$

Output

Output the answer.

Constraints

• $1 \leq N \leq 3\times 10^5$
• $-10^9 \leq A_i \leq 10^9$
• $A_i\neq 0$
• The $A_i$ are distinct.
• All input values are integers.

4
-1 -4 2 -11

23

Takahashi acts as follows.

• He moves from coordinate $0$ to coordinate $-1$ and picks up the cookie. The distance traveled is $1$.
• He moves from coordinate $-1$ to coordinate $-4$ and picks up the cookie. The distance traveled is $3$.
• He moves from coordinate $-4$ to coordinate $2$ and picks up the cookie. The distance traveled is $6$.
• He moves from coordinate $2$ to coordinate $-11$ and picks up the cookie. The distance traveled is $13$.

Thus, the total distance traveled is $1+3+6+13=23$.

In the second action, the distances to the cookie at coordinate $-4$ and the cookie at coordinate $2$ are both $3$, and Takahashi moves to $-4$, the smaller coordinate.

10
1 2 3 4 5 -1 -2 -3 -4 -6

17

• Source: AtCoder ABC 471 C