2010: 放牧
内存限制：256 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：3
解决：3
题目描述
Anna是一个宠物迷，她有N (2 <= N <= 1,500) 只良种宠物兔，编号1到N。Anna的父亲SSS还特别为她建造一个新的兔舍。她刚油漆一新的兔舍有S间小房间S (N <= S <= 1,000,000)，这S间房间编号分别为1到S，且排成长长一排，每个房间离隔壁房间1个单位。
休息时兔子们每只单独呆一间，兔子i住在房间P_i。由于不擅长交际，兔子们相互之间离太近就会脾气暴躁，所以Anna决定将她的句子们尽可能地分开。
Anna要确保这N-1两两相邻的兔子之间的距离尽可能的大且尽可能的平均。
特别地，Anna希望任意两只相邻的兔子之间的距离最多与(S-1)/(N-1)相差1，这里的“/”为整数除，而且她希望两两兔子之间的距离尽可能多地等于(S-1)/(N-1)。因此，对于4只兔子8个房间，一种安排兔子的方式为放置位置为（1, 3, 5, 8）或（1, 3, 6, 8），但是（1, 2, 4, 7）或（1, 2, 4, 8）是不符合Anna要求的。
请你编写一个程序，通过计算尽可能高效地将这些兔子分开，且得出最小的总移动距离，使得实现适当的分隔。兔子进入或离开一个房间距离忽略不计。
休息时兔子们每只单独呆一间，兔子i住在房间P_i。由于不擅长交际，兔子们相互之间离太近就会脾气暴躁，所以Anna决定将她的句子们尽可能地分开。
Anna要确保这N-1两两相邻的兔子之间的距离尽可能的大且尽可能的平均。
特别地，Anna希望任意两只相邻的兔子之间的距离最多与(S-1)/(N-1)相差1，这里的“/”为整数除，而且她希望两两兔子之间的距离尽可能多地等于(S-1)/(N-1)。因此，对于4只兔子8个房间，一种安排兔子的方式为放置位置为（1, 3, 5, 8）或（1, 3, 6, 8），但是（1, 2, 4, 7）或（1, 2, 4, 8）是不符合Anna要求的。
请你编写一个程序，通过计算尽可能高效地将这些兔子分开，且得出最小的总移动距离，使得实现适当的分隔。兔子进入或离开一个房间距离忽略不计。
输入
* Line 1: N和S,之间有一个空格隔开。
* Lines 2..N+1: 第i+1行包含一个整数P_i。
输出
* Line 1: 一个整数，表示最少移动兔子的距离，该数不会超过1,000,000,000
样例输入 复制
5 10
2
8
1
3
9
样例输出 复制
4提示
【输入详细说明】 1 2 3 4 5 6 7 8 9 10兔子位置 | A | B | C | . | . | . | . | D | E | . |【输出详细说明】兔子们从房间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 |