등차수열

$N$개의 항을 가진 수열 $A$가 있다. 각 항에 $1$을 더하거나 빼는 연산을 수행할 수 있다. 단, 이 연산은 항 하나에 최대 한 번만 적용 가능하다. 즉, $A$의 $i$번째 항의 값이 초기에 $x$로 주어졌다면, 최종적으로 $i$번째 항의 값은 연산을 수행하지 않은 경우에는 $x$, 연산을 수행한 경우에는 $x + 1$ 혹은 $x - 1$중 하나가 가능하다.

최소한의 연산으로 수열 $A$가 공차 $1$인 등차수열이 되도록 만드는 프로그램을 작성하라.

여기서 공차 $1$인 등차수열이라 함은, $1 \le i < N$인 모든 정수 $i$에 대해, $i + 1$번째 항 $A_{i+1}$에서 $i$번째 항 $A_i$를 뺀 값이 $A_{i+1} - A_i = 1$임을 뜻한다.

입력 형식

첫 줄에 수열의 길이를 나타내는 정수 $N$이 주어진다. ($1 \le N \le 100\,000$)

그다음 줄에 수열의 $N$개의 항의 초깃값이 공백으로 구분되어 차례대로 주어진다. 이 값은 모두 $1$ 이상 $1\,000\,000\,000$ 이하의 정수다.

항상 연산을 적절히 사용하여 공차 $1$인 등차수열을 만들 수 있는 경우만 입력으로 주어진다.

출력 형식

첫 줄에 최소 연산 횟수를 출력한다.

예제

5
1 3 4 5 5

2

예제 설명

한 번의 연산으로 수열의 첫 번째 값을 $2$로 바꾸고, 또 한 번의 연산으로 수열의 마지막 값을 $6$으로 바꾸는 것이 최적이다. 이 경우, 최종적으로 수열은 $[2, 3, 4, 5, 6]$이 된다.

채점 방식

입력 케이스들은 다음과 같은 종류로 구별되며, 한 종류의 케이스를 다 맞혀야 그 종류에 배정된 점수를 받을 수 있다.

해설