/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 500 点
問題文
長さ N の整数列 A=(A_1,A_2,\dots,A_N) が与えられます。
あなたは A を自由に並び替えることが出来ます。並び替えた後の \sum_{i=1}^{N-1} ((A_{i+1} - A_i) \bmod K) としてあり得る最大値を求めてください。
ここで、x \bmod K とは 0 \le y < K かつ x - y が K の倍数になる整数 y のことを指します。例えば、-3 \bmod 8 = 5,9 \bmod 6 = 3 となります。
制約
- 2 \le N \le 2 \times 10^5
- 1 \le K \le 10^9
- 0 \le A_i < K
入力
入力は以下の形式で標準入力から与えられる。
N K A_1 A_2 \dots A_N
出力
答えを出力せよ。
入力例 1
3 4 0 1 2
出力例 1
6
最適な例として、A = (2,1,0) と並び替えると (1 - 2) \bmod 4 + (0 - 1) \bmod 4 = 3 + 3 = 6 が達成できます。
入力例 2
7 123 11 34 56 0 32 100 78
出力例 2
638
Score : 500 points
Problem Statement
You are given an integer sequence A=(A_1,A_2,\dots,A_N) of length N.
You can rearrange A freely. Find the maximum value that \sum_{i=1}^{N-1} ((A_{i+1} - A_i) \bmod K) can take after rearranging.
Here, x \bmod K denotes the integer y such that 0 \le y < K and x - y is a multiple of K. For example, -3 \bmod 8 = 5, and 9 \bmod 6 = 3.
Constraints
- 2 \le N \le 2 \times 10^5
- 1 \le K \le 10^9
- 0 \le A_i < K
Input
The input is given from Standard Input in the following format:
N K A_1 A_2 \dots A_N
Output
Print the answer.
Sample Input 1
3 4 0 1 2
Sample Output 1
6
One optimal solution is to rearrange A into (2,1,0) to achieve (1 - 2) \bmod 4 + (0 - 1) \bmod 4 = 3 + 3 = 6.
Sample Input 2
7 123 11 34 56 0 32 100 78
Sample Output 2
638