After completing his physics lab, Lucas is tasked with creating a graph to illustrate his collected data. Lucas has gathered an array of $N$ data points, $A_1,A_2,\dots ,A_N$, that are evenly spaced along the $x$-axis. Based on his research, Lucas knows that the data should be linear, with equal differences between adjacent data points. As a perfectionist, Lucas wants to create a graph that depicts this linear relationship, but he feels guilty about modifying the data too much. He has decided that he will only shift a group of contiguous data points all up or all down by $1$ in a single operation. What is the minimum number of operations Lucas will need to perform to make his data linear?

Constraints

$1\le N\le {10}^6$

${-10}^9\le A_i\le {10}^9$

Input Specification

The first line contains $N$.

The next line contains $N$ space-separated integers, $A_1,A_2,\dots ,A_N$.

Output Specification

Output the minimum number of operations needed.

Sample Input 1

5
1 2 4 6 10

Sample Output 1

2

Explanation for Sample Output 1

First, increase the subarray $[2,4,6]$ by $1$. The data becomes $[1,3,5,7,10]$.

Next, decrease the subarray $[10]$ by $1$. The data becomes $[1,3,5,7,9]$.

It can be proven that $2$ is the minimum number of operations needed.

Sample Input 2

5
-2 -1 1 6 9

Sample Output 2

3

Explanation for Sample Output 2

First, increase the subarray $[-1,1]$ by $1$. The data becomes $[-2,0,2,6,9]$.

Next, increase the subarray $[0,2]$ by $1$. The data becomes $[-2,1,3,6,9]$.

Finally, decrease the subarray $[-2,1]$ by $1$. The data is now $[-3,0,3,6,9]$.

It can be proven that $3$ is the minimum number of operations needed.