Description

Farmer John has $N$ cows, numbered $1..N$, where $2 \le N \le 1500$. His newly painted barn has $S$ stalls in a single line, numbered $1..S$, where $N \le S \le 1{,}000{,}000$. Each pair of adjacent stalls is at distance $1$.

The cows have already gone to rest; cow $i$ is currently in stall $P_i$. Since cows get grumpy when they are too close together, Farmer John wants to move them so they are as spread out as possible and with similar gaps.

Let $d = \left\lfloor \frac{S - 1}{N - 1} \right\rfloor$ (integer division). Farmer John wants the $N - 1$ distances between adjacent cows to each differ from $d$ by at most $1$, and he also wants to maximize the number of these distances that are exactly equal to $d$.

For example, with $4$ cows and $8$ stalls, placements $1, 3, 5, 8$ and $1, 3, 6, 8$ are allowed, but $1, 2, 4, 7$ and $1, 2, 4, 8$ are not allowed.

Help Farmer John spread the cows as efficiently as possible by computing the minimum total distance the cows must move to achieve such spacing. Ignore the distance for entering or leaving a stall.

Input Format

• Line 1: Two space-separated integers $N$ and $S$.
• Lines $2..N+1$: Line $i+1$ contains a single integer $P_i$.

Output Format

• Line 1: A single integer — the minimum total distance the cows must travel. This value is guaranteed to be less than $1{,}000{,}000{,}000$.

5 10 
2 
8 
1 
3 
9 

4 

Hint

1 2 3 4 5 6 7 8 9 10 Cow Locs | A | B | C | . | . | . | . | D | E | . |

Cows move from stall 2 to 3, 3 to 5, and 9 to 10. The total distance moved is 1 + 2 + 1 = 4. The final positions of the cows are in stalls 1, 3, 5, 8, and 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 |

Translated by ChatGPT 5