Warp Points

You are building an interstellar transportation network. There are $N$ stars in your region, and your task is to make it possible to travel from any star to any other star. Right now all the stars are isolated, so no star can reach any other star.

As a designer of the interstellar transportation network, you can set warp points. The stars are numbered from $1$ to $N$, and a warp point lets you come and go between stars with consecutive numbers. The construction cost of a warp point depends on the "potentials" of the stars and of the warp point. The potential of the $i$-th star is given as an integer, and you can set the potential of the warp point to any integer. The cost is the sum of the absolute differences between the warp point's potential and the potential of each star it contains.

You can construct any number of warp points. Compute the minimum total cost to make it possible to travel between any pair of stars using some warp points.

For sample input 1, the best plan is to construct one warp point with potential 2.

For sample input 2, three warp points are needed to minimize the total cost. The first warp point connects the first star through the fourth star. The second warp point connects the fourth star through the sixth star. The third warp point connects the sixth star through the tenth star.

The input consists of a single test case in the following format.

$N$

$a_1$ $\dots$ $a_N$

$N$ is the number of stars ($1 \le N \le 3,000$). The values $a_1$ through $a_N$ are the potentials of the stars. Each potential is guaranteed to be an integer between $-1,000,000,000$ and $1,000,000,000$.

Output the minimum total cost to connect all the stars.