Optimal Cow Spacing

Farmer John has N prize milk cows and S stalls arranged in a row. The cows are currently in stalls given by P_i (not necessarily sorted) and Farmer John wishes to reposition them so that they are as evenly spaced as possible. In particular, let \[ d = \left\lfloor \frac{S-1}{N-1} \right\rfloor \] Farmer John requires that the distance between any two consecutive cows is either \(d\) or \(d+1\), and that the number of gaps exactly equal to \(d\) is maximized. Equivalently, if the valid repositioning uses exactly \(r\) gaps of length \(d+1\) then \[ r = (S-1) - (N-1)\,d, \qquad 0 \le r < N-1. \] Moreover, the repositioning must use stalls within the range \([1, S]\) and the leftmost cow must be placed in stall 1 and the rightmost in stall S so that the spacing stretches the full barn.

If we denote the final positions of the cows (in increasing order) by \(x_1, x_2, \dots, x_N\), then we must have \[ x_1 = 1, \qquad x_N = S, \qquad \text{and} \qquad x_{i+1} - x_i \in \{d, d+1\} \text{ for } 1 \le i < N. \]

Your task is to choose one valid sequence of final positions so that when the cows (which may be moved arbitrarily, but without reordering them) are reassigned to these stalls (in sorted order) the total movement distance, defined by \(\sum_{i=1}^{N} |P_i - x_i|\), is minimized.

Note: There may be many valid final sequences (depending on the order in which the extra \(+1\) gaps are inserted) but you must choose one that minimizes the overall movement cost.

inputFormat

The first line contains two integers \(N\) and \(S\) (with \(2 \le N \le 1500\) and \(N \le S \le 10^6\)). The second line contains \(N\) integers \(P_1, P_2, \dots, P_N\) representing the current stall positions of the cows.

outputFormat

Output a single integer: the minimum total distance the cows must be moved so that the final cow placements satisfy the above spacing requirements.

sample

4 8
1 3 6 8

0