Gromozek has a sequence of integers
A of length
N. It freely chooses the integer
b. Here he will become sad if
Ai and
b+i are far apart. More precisely, Gromozeka's sadness is calculated as follows:
\(abs(A_1-(b+1))+abs(A_2-(b+2))+...+abs(A_N-(b+N))\) .
Here
\(abs(x) \) is a function that returns the absolute value of
x. Find Gromozeka's minimum possible sadness.
Input
The first line contains an integer
N (
\(1<=N<=2 \cdot 10^5\)). The second line contains
N integers
Ai (
\(1<=A_i<=10 ^9\)).
Imprint
Display Gromozeka's minimum possible sadness.
Examples
| # |
Input |
Output |
Explanation |
| 1 |
5
2 2 3 5 5
| 2 |
If we choose b = 0, Gromozeka's sadness will be \(\)
abs (2- (0 + 1)) + abs (2-(0 + 2))+ abs (3-(0 + 3)) + abs (5- (0 + 4)) + abs(5-(0 + 5)) = 2.
Any other choice of b does not make Gromozeka's sadness less than 2, so the answer is 2. |
| 2 |
9
1 2 3 4 5 6 7 8 9
| 0 |
|
| 3 |
6
6 5 4 3 2 1
| 18 |
|
| 4 |
7
1 1 1 1 2 3 4
| 6 |
|