소 고르게 배치하기

농부 존은 $1$번부터 $N$번까지 번호가 매겨진 젖소 $N$마리를 기르고 있습니다. 새로 칠한 외양간에는 $1$번부터 $S$번까지 번호가 매겨진 칸이 한 줄로 놓여 있으며, 이웃한 두 칸 사이의 거리는 모두 $1$입니다.

소들은 쉬려고 칸으로 들어갔습니다. $i$번 소는 $P_i$번 칸에 있습니다. 소들은 서로 너무 가까이 있으면 예민해지기 때문에, 존은 소들을 최대한 넓게 퍼뜨리려고 합니다.

존은 인접한 두 소 사이의 $N-1$개의 거리를 가능한 한 크게, 그리고 서로 비슷하게(거의 같은 간격으로) 만들고 싶어 합니다. 구체적으로 $D = \lfloor (S-1)/(N-1) \rfloor$ (정수 나눗셈)라고 할 때, 인접한 소 사이의 모든 거리는 $D$와의 차이가 최대 $1$이어야 하며, 그중 정확히 $D$와 같은 거리가 가능한 한 많아야 합니다.

예를 들어 소가 $4$마리이고 칸이 $8$개라면 소를 $1, 3, 5, 8$ 또는 $1, 3, 6, 8$에 놓을 수는 있지만, $1, 2, 4, 7$ 이나 $1, 2, 4, 8$ 에는 놓을 수 없습니다.

이렇게 소들을 배치하기 위해 소들이 움직여야 하는 최소 총 이동 거리를 구하세요. 소가 칸에 들어가고 나오는 거리는 무시합니다.

• 첫째 줄: 두 정수 $N$ 과 $S$ 가 공백으로 구분되어 주어집니다.
• 둘째 줄부터 $N+1$째 줄까지: $i+1$째 줄에 정수 $P_i$ 가 하나씩 주어집니다.

제약: $2 \le N \le 1500$, $N \le S \le 1000000$, $1 \le P_i \le S$.

• 첫째 줄에 소들이 움직여야 하는 최소 총 이동 거리를 정수 하나로 출력합니다. 이 값은 항상 1,000,000,000 미만이며 부호 있는 32비트 정수에 충분히 들어갑니다.

아래 그림은 소 $5$마리를 칸 $10$개에 배치하는 상황(처음 위치 $1, 2, 3, 8, 9$)을 보여 줍니다.

               1   2   3   4   5   6   7   8   9  10
Cow Locs     | 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
Init Stall     | A | B | C | . | . | . | . | D | E | . |
Final Stall    | A | . | B | . | C | . | . | D | . | E |
Distance moved | 0 | . | 1 | . | 2 | . | . | 0 | . | 1 |