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 \leq N \leq {10}^{6}~

~{-10}^{9} \leq A_i \leq {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.