771. [USACO Open09] 放牧2

FJ有N(2 <= N <= 1,500)个引以为荣的奶牛，编号为1～N，他刚刚粉刷过的牛棚有S(N <= S <= 1,000,000)个栏位，编号为1～S，这些栏位排成一长排，相邻两个栏位之间的间距为1。

奶牛要走回他们的栏位去休息，第i头牛的栏位编号为P_i，这些牛都不太擅于交际，如果互相之间栏位离的太近就会发牛脾气，因此FJ必须得把她们弄得尽可能分散一些。

FJ想使得这N-1个相邻牛的间距尽可能的大，并且他还希望间距能尽量接近。

特别地，FJ希望所有的相邻间距都至少为1，并且不超过(S - 1) / (N - 1),（此处为整除），并且这些间距越接近(S - 1) / (N - 1)越好（整除）。比如，有4头牛8个栏位，可以将牛的分布布置成1，3，5，8或者1，3，6，8，但不能是1，2，4，7或者1，2，4，8。

帮助FJ快速地将这些牛分散开来，并输出为达到这个合适的位置所有牛移动的距离总和，牛进入或离开栏位的距离可忽略不计。


输入格式：
第1行：两个空格隔开的整数N，S；
第2～N+1行：第i+1行有一个整数P_i；

输出格式：
一行，一个整数，即所有牛必须移动的距离和的最小值。答案保证小于1,000,000,000。

输入输出样例：
graze2.in
5 10
2
8
1
3
9

输入样例说明：
1   2   3   4   5   6   7   8   9   10
起初牛的分布 | A | B | C | . | . | . | . | D | E | . |

graze2.out
4

输出样例解释：
牛的移动为：2->3,3->5,9->10,总的移动距离为1+2+1=4，最终牛所在的栏位为1，3，5，8，10。

               1   2   3   4   5   6   7   8   9   10 
起初牛所在栏位 | A | B | C | . | . | . | . | D | E | . |
最终牛所在栏位 | A | . | B | . | C | . | . | D | . | E |
移动的距离     | 0 | . | 1 | . | 2 | . | . | 0 | . | 1 |