
After completing his physics lab, Lucas is tasked with creating a graph to illustrate his collected data. Lucas has gathered an array of
data points,
, that are evenly spaced along the
-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
in a single operation. What is the minimum number of operations Lucas will need to perform to make his data linear?
Constraints


Input Specification
The first line contains
.
The next line contains
space-separated integers,
.
Output Specification
Output the minimum number of operations needed.
Sample Input 1
Copy
5
1 2 4 6 10
Sample Output 1
Copy
2
Explanation for Sample Output 1
First, increase the subarray
by
. The data becomes
.
Next, decrease the subarray
by
. The data becomes
.
It can be proven that
is the minimum number of operations needed.
Sample Input 2
Copy
5
-2 -1 1 6 9
Sample Output 2
Copy
3
Explanation for Sample Output 2
First, increase the subarray
by
. The data becomes
.
Next, increase the subarray
by
. The data becomes
.
Finally, decrease the subarray
by
. The data is now
.
It can be proven that
is the minimum number of operations needed.
Comments