D. Cookie's Candy
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

As part of Halloween tradition, Cookie Sigma is going trick or treating (even though he might be a little too old for it now)! Specifically, he is trick or treating on Permutation Avenue, where the addresses of all of the houses are a permutation!

More formally, there is a permutation* $$$a$$$ of $$$n$$$ $$$(2 \leq n \leq 5000)$$$ houses, where $$$a_i$$$ is the address of house $$$i$$$.

As a number enthusiast, Cookie Sigma wants to visit the houses in increasing order of their addresses — that is, he wants to visit address $$$1$$$, then $$$2$$$, and so on, up to $$$n$$$. However, going strictly in that order can be very inefficient, since the houses might be far apart on the street.

To make his route shorter, Cookie Sigma can perform at most one swap in his visiting order — meaning he may choose two addresses and swap the order in which he visits them (possibly performing no swap at all).

The total distance Cookie Sigma has to travel is the sum of distances between consecutive houses in his visiting order. Formally, if the $$$x$$$-th house Cookie Sigma visits is located at index $$$p_x$$$, then the total distance is defined as:

Total Distance = $$$\sum_{x=1}^{n-1} |p_{x+1} - p_x|$$$.

Note that Cookie Sigma starts at the first house he plans on visiting, so there is no travel cost to get there.

Find the minimum total distance he can achieve.

* A permutation of length $$$n$$$ is an array consisting of $$$n$$$ distinct integers from $$$1$$$ to $$$n$$$ in arbitrary order. For example, $$$[2, 3, 1, 5, 4]$$$ is a permutation, but $$$[1, 2, 2]$$$ is not a permutation ($$$2$$$ appears twice in the array), and $$$[1, 3, 4]$$$ is also not a permutation ($$$n = 3$$$ but there is $$$4$$$ in the array).

Input

The first line contains an integer $$$n$$$ $$$(2 \leq n \leq 5000)$$$ — the number of houses on Permutation Avenue

The second line contains $$$n$$$ numbers, $$$a_1, a_2, \dots, a_n$$$ $$$(1 \leq a_i \leq n)$$$ — the addresses of the houses on Permutation Avenue

Output

Output a single number, the minimum total distance Cookie Sigma can achieve.

Examples
Input
4
2 4 1 3
Output
5
Input
4
1 2 3 4
Output
3
Note

In the first test case, we can swap when we go to house $$$1$$$ and $$$4$$$, meaning our visiting order is $$$[4, 2, 3, 1]$$$.

  • Distance from $$$4$$$ -> $$$2$$$ = $$$|2 - 1|$$$ = 1
  • Distance from $$$2$$$ -> $$$3$$$ = $$$|1 - 4|$$$ = 3
  • Distance from $$$3$$$ -> $$$1$$$ = $$$|4 - 3|$$$ = 1 is not.
  • $$$1 + 3 + 1 = 5$$$

It can be proven that this is the minimum total distance we can achieve.

In the second test case, we can leave our visiting order as is and perform no swaps. Going in order yields a total distance of $$$3$$$ which is optimal.