B - 待ち合わせ場所 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 300 点

問題文

高橋君は N 人の友人と待ち合わせをすることになりました。

友人たちは数直線上に位置しており、 i 番目の友人は座標 X_i にいます（異なる友人が同じ座標にいることもあります）。

高橋君は待ち合わせ場所を 1 か所だけ決めようとしています。待ち合わせ場所を数直線上の整数座標 P に設定すると、各友人はその場所まで移動します。このとき、友人全員の移動距離の合計を「総移動距離」と呼びます。すなわち、総移動距離は |X_1 - P| + |X_2 - P| + \cdots + |X_N - P| です。なお、高橋君自身の移動距離は総移動距離に含みません。

高橋君は、友人たちの負担をできるだけ減らすため、P を最適に選んで総移動距離を最小にしたいと考えています。

総移動距離の最小値を求めてください。

制約

  • 1 \leq N \leq 2 \times 10^5
  • -10^9 \leq X_i \leq 10^9
  • 入力はすべて整数

入力

N
X_1 X_2 \cdots X_N
  • 1 行目には、友人の人数を表す整数 N が与えられる。
  • 2 行目には、各友人の座標を表す整数 X_1, X_2, \ldots, X_N がスペース区切りで与えられる。

出力

総移動距離の最小値を整数で 1 行に出力せよ。

入力例 1

3
1 2 10

出力例 1

9

入力例 2

4
0 0 5 9

出力例 2

14

入力例 3

10
-12 4 7 -3 0 9 9 15 -8 2

出力例 3

65

入力例 4

20
12 -5 30 7 7 -18 42 0 3 3 3 50 -1 9 -15 100 -40 8 21 21

出力例 4

363

入力例 5

1
-1000000000

出力例 5

0

Score : 300 pts

Problem Statement

Takahashi is going to meet up with N friends.

His friends are located on a number line, and the i-th friend is at coordinate X_i (different friends may be at the same coordinate).

Takahashi wants to decide on exactly one meeting place. If he sets the meeting place at an integer coordinate P on the number line, each friend will travel to that location. The sum of all friends' travel distances is called the "total travel distance." That is, the total travel distance is |X_1 - P| + |X_2 - P| + \cdots + |X_N - P|. Note that Takahashi's own travel distance is not included in the total travel distance.

Takahashi wants to minimize the total travel distance by choosing P optimally, in order to reduce the burden on his friends as much as possible.

Find the minimum value of the total travel distance.

Constraints

  • 1 \leq N \leq 2 \times 10^5
  • -10^9 \leq X_i \leq 10^9
  • All inputs are integers.

Input

N
X_1 X_2 \cdots X_N
  • The first line contains an integer N, representing the number of friends.
  • The second line contains integers X_1, X_2, \ldots, X_N separated by spaces, representing the coordinates of each friend.

Output

Print the minimum value of the total travel distance as an integer on a single line.

Sample Input 1

3
1 2 10

Sample Output 1

9

Sample Input 2

4
0 0 5 9

Sample Output 2

14

Sample Input 3

10
-12 4 7 -3 0 9 9 15 -8 2

Sample Output 3

65

Sample Input 4

20
12 -5 30 7 7 -18 42 0 3 3 3 50 -1 9 -15 100 -40 8 21 21

Sample Output 4

363

Sample Input 5

1
-1000000000

Sample Output 5

0