ibasic은 디미고의 부지인 광덕산이 마음에 들지 않아 새로운 산을 그리기로 했다.
ibasic이 그린 산은 $2$차원 평면 위의 $N+1$개의 점 $(0, h_0), (1, h_1), \ldots, (N, h_N)$으로 표현할 수 있다. 모든 $h_i$는 음이 아닌 정수이며 $h_0 = h_N = 0$이다.
ibasic은 자신이 그린 산을 아름다운 강산으로 만들고자 한다. 아름다운 강산은 $1 \le i \le N$인 모든 $i$에 대해 $|h_i - h_{i-1}| = 1$인 산이다.
ibasic은 자신이 그린 산을 아름다운 강산으로 만들기 위해 그림을 다음과 같이 수정할 수 있다.
- $1 \le l \le r \le N-1$인 두 정수 $l$, $r$을 골라 $h_l, h_{l+1}, \ldots, h_{r}$에 $1$을 더한다.
- $1 \le l \le r \le N-1$인 두 정수 $l$, $r$을 골라 $h_l, h_{l+1}, \ldots, h_{r}$에 $1$을 뺀다.
그림을 수정하다가 그림이 망가지면 안 되기 때문에 그림을 수정한 뒤에도 모든 $h_i$는 $0$ 이상이어야 한다.
그림을 수정하는 것은 상당히 귀찮은 작업이므로 ibasic은 그림을 최소한으로 수정하기로 했다. ibasic이 그린 산을 아름다운 강산으로 만들기 위해 그림을 최소 몇 번 수정해야 하는지 구하시오.
Input
첫 번째 줄에 정수 $N$이 주어진다. $(2\le N\le 10^6)$
두 번째 줄에 산을 나타내는 $N+1$개의 정수 $h_0, h_1, \ldots, h_N$이 공백으로 구분되어 주어진다. $(0 \le h_i \le 10^9;$ $h_0 = h_N = 0)$
Output
첫 번째 줄에 ibasic이 그린 산을 아름다운 강산으로 만들기 위해 필요한 최소 수정 횟수를 출력한다. 단, 수정을 어떻게 해도 ibasic이 그린 산을 아름다운 강산으로 만들 수 없다면 -1을 대신 출력한다.
Examples
Input 1
4 0 3 2 4 0
Output 1
3
Input 2
5 0 3 2 5 9 0
Output 2
-1