C - Organizing the Bookshelf Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

高橋君は自分の部屋の本棚を整理することにしました。本棚には N 冊の本があり、i 番目（1 \leq i \leq N）の本の厚さは V_i です。異なる番号の 2 冊の本の厚さが同じである場合もあります。

高橋君は、N 冊の本すべてをちょうど 1 回ずつ使い、任意の順番で一列に並べ替えようとしています。隣り合う本の厚さの差が大きいと見た目が悪いと感じるため、隣り合う本の厚さの差の絶対値の総和ができるだけ小さくなるように並べ替えたいと考えました。

具体的には、並べ替えた結果、左から k 番目の本の厚さを A_k とします。ここで (A_1, A_2, \ldots, A_N) は (V_1, V_2, \ldots, V_N) を並べ替えたものです。このとき、

\sum_{k=1}^{N-1} |A_k - A_{k+1}|

の値の最小値を求めてください。

制約

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq V_i \leq 10^9
  • 入力はすべて整数である

入力

N
V_1 V_2 \ldots V_N
  • 1 行目には、本の冊数を表す整数 N が与えられる。
  • 2 行目には、各本の厚さを表す N 個の整数 V_1, V_2, \ldots, V_N がスペース区切りで与えられる。

出力

隣り合う本の厚さの差の絶対値の総和の最小値を整数として 1 行で出力せよ。

入力例 1

4
3 1 4 2

出力例 1

3

入力例 2

7
10 50 30 20 40 5 25

出力例 2

45

入力例 3

10
1000000000 1 500000000 250000000 750000000 100 999999999 2 123456789 987654321

出力例 3

999999999

Score : 300 pts

Problem Statement

Takahashi has decided to organize the bookshelf in his room. The bookshelf contains N books, and the thickness of the i-th book (1 \leq i \leq N) is V_i. Two books with different indices may have the same thickness.

Takahashi wants to rearrange all N books into a single row in any order, using each book exactly once. Since a large difference in thickness between adjacent books looks unappealing, he wants to rearrange the books so that the sum of absolute differences of thicknesses between adjacent books is minimized.

Specifically, let A_k denote the thickness of the k-th book from the left after rearranging. Here, (A_1, A_2, \ldots, A_N) is a permutation of (V_1, V_2, \ldots, V_N). Find the minimum value of:

\sum_{k=1}^{N-1} |A_k - A_{k+1}|

Constraints

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq V_i \leq 10^9
  • All input values are integers.

Input

N
V_1 V_2 \ldots V_N
  • The first line contains an integer N, representing the number of books.
  • The second line contains N integers V_1, V_2, \ldots, V_N separated by spaces, representing the thickness of each book.

Output

Print the minimum value of the sum of absolute differences of thicknesses between adjacent books as an integer on a single line.

Sample Input 1

4
3 1 4 2

Sample Output 1

3

Sample Input 2

7
10 50 30 20 40 5 25

Sample Output 2

45

Sample Input 3

10
1000000000 1 500000000 250000000 750000000 100 999999999 2 123456789 987654321

Sample Output 3

999999999