/ 
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 300 点
問題文
数直線上の N 箇所にクッキーが落ちています。i 番目のクッキーの落ちている座標は A_i です。
高橋君は最初、数直線の座標 0 にいて、N 個のクッキー全てを拾うまで以下の行動を繰り返します。
- 行動：自身から最も近いクッキーのある座標(複数あるときは座標の最も小さいもの)へ移動し、そのクッキーを拾う。
全てのクッキーを拾うまでの高橋君の移動距離の合計を求めてください。
制約
- 1 \leq N \leq 3\times 10^5
- -10^9 \leq A_i \leq 10^9
- A_i\neq 0
- A_i は相異なる
- 入力は全て整数である
入力
入力は以下の形式で標準入力から与えられる。
N A_1 \dots A_N
出力
答えを出力せよ。
入力例 1
4 -1 -4 2 -11
出力例 1
23
高橋君は以下のように行動します。
- 座標 0 から座標 -1 へ移動しクッキーを拾う。移動距離は 1 である。
- 座標 -1 から座標 -4 へ移動しクッキーを拾う。移動距離は 3 である。
- 座標 -4 から座標 2 へ移動しクッキーを拾う。移動距離は 6 である。
- 座標 2 から座標 -11 へ移動しクッキーを拾う。移動距離は 13 である。
よって、移動距離の合計は 1+3+6+13=23 となります。
2 回目の行動において、座標 -4 にあるクッキーと座標 2 にあるクッキーまでの距離はともに 3 ですが、高橋君は座標の小さい -4 の方へ移動します。
入力例 2
10 1 2 3 4 5 -1 -2 -3 -4 -6
出力例 2
17
Score : 300 points
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.
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.
Input
The input is given from Standard Input in the following format:
N A_1 \dots A_N
Output
Output the answer.
Sample Input 1
4 -1 -4 2 -11
Sample Output 1
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.
Sample Input 2
10 1 2 3 4 5 -1 -2 -3 -4 -6
Sample Output 2
17