分数: 500 点
问题陈述
给你一个整数序列 A=(A_1,A_2,\dots,A_N) 长度 N.
您可以重新排列 A 自由。找到最大值 \sum_{i=1}^{N-1} ((A_{i+1} - A_i) \bmod K) 重新排列后即可拍摄。
在这里, x \bmod K 表示整数 y 这样 0 \le y < K 和 x - y 是以下的倍数 K。例如, -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