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).
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 a single number, the minimum total distance Cookie Sigma can achieve.
42 4 1 3
5
41 2 3 4
3
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]$$$.
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.
