Utility Poles

There are $N$ utility poles standing in a row on a straight line. Treat the line as the $x$-axis and let the pole positions be the $x$-coordinates $x_0, x_1, \dots, x_{N-1}$. Always $x_0 = 0$, every $x_i$ with $i \ge 1$ is a positive integer, and the coordinates are distinct and given in increasing order.

You want to move some of the poles so that the gap between every pair of neighboring poles becomes equal, while keeping the total moved distance as small as possible. The pole at $x_0 = 0$ is fixed and cannot move, and any pole you move must land on an integer coordinate.

The order of the poles never changes, so in the final arrangement the $i$-th pole from the left (counting from $0$) sits at coordinate $i \cdot d$, where $d$ is the common gap between neighboring poles and is a positive integer.

For example, suppose the poles are at coordinates $0, 4, 6, 9$.

If you make the gap $4$ by moving the poles at $6$ and $9$ to $8$ and $12$, the total moved distance is $2 + 3 = 5$.

But if you move only the pole at $4$ to $3$, every gap becomes $3$ and the total moved distance is just $1$.

Given the positions of the poles, write a program that finds the minimum total moved distance needed to make all neighboring gaps equal, with $x_0$ fixed.

The first line contains the number of poles $N$ ($1 \le N \le 100000$).

The second line contains the distinct $x$-coordinates $x_0, x_1, \dots, x_{N-1}$, separated by spaces and given in increasing order. Every $x_i$ is an integer, $x_0 = 0$, and $1 \le x_i \le 10^9$ for $i \ge 1$.

Print, on a single line, the minimum total moved distance when the poles are shifted so that all neighboring gaps are equal.

Intermediate values and the answer can exceed the range of a 32-bit integer, so using a 64-bit integer type is recommended.