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
5
1 2 4 6 10
Sample Output 1
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
5
-2 -1 1 6 9
Sample Output 2
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