Spreading Out the Cows

Farmer John keeps $N$ prize milk cows numbered $1$ through $N$. His freshly painted barn has $S$ stalls numbered $1$ through $S$ laid out in a single line, and every pair of neighboring stalls is exactly $1$ unit of distance apart.

The cows have settled into the stalls to rest: cow $i$ is in stall $P_i$. Because the cows are antisocial and get grumpy when packed too close together, Farmer John wants to move them so they are as spread out as possible.

He wants the $N-1$ distances between adjacent cows to be as large as possible and also as uniform as possible (close to equal spacing). Concretely, let $D = \lfloor (S-1)/(N-1) \rfloor$ using integer division. Every distance between adjacent cows must differ from $D$ by at most $1$, and as many of those distances as possible must equal exactly $D$.

For instance, with four cows and eight stalls the cows may be placed at $1, 3, 5, 8$ or $1, 3, 6, 8$, but not at $1, 2, 4, 7$ or $1, 2, 4, 8$.

Compute the minimum total distance the cows must move to achieve such a spacing. Ignore the distance a cow needs to enter or leave a stall.

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

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

• A single integer: the minimum total distance the cows must travel. This value is guaranteed to be under 1,000,000,000, so it fits comfortably in a signed 32-bit integer.

The diagram below illustrates a barn with $5$ cows and $10$ stalls whose starting positions are $1, 2, 3, 8, 9$.

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

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