ibasic n'aime pas le mont Gwangdeok, où se situe le Dimigo, et a décidé de dessiner une nouvelle montagne.
La montagne dessinée par ibasic peut être représentée par $N+1$ points sur un plan bidimensionnel : $(0, h_0), (1, h_1), \ldots, (N, h_N)$. Tous les $h_i$ sont des entiers non négatifs et $h_0 = h_N = 0$.
ibasic souhaite transformer sa montagne en une belle montagne. Une belle montagne est une montagne telle que $|h_i - h_{i-1}| = 1$ pour tout $i$ tel que $1 \le i \le N$.
Pour transformer sa montagne en une belle montagne, ibasic peut modifier son dessin de la manière suivante :
- Choisir deux entiers $l$ et $r$ tels que $1 \le l \le r \le N-1$ et ajouter $1$ à $h_l, h_{l+1}, \ldots, h_{r}$.
- Choisir deux entiers $l$ et $r$ tels que $1 \le l \le r \le N-1$ et soustraire $1$ à $h_l, h_{l+1}, \ldots, h_{r}$.
Comme il ne faut pas gâcher le dessin, tous les $h_i$ doivent rester supérieurs ou égaux à $0$ après chaque modification.
Modifier le dessin est une tâche fastidieuse, c'est pourquoi ibasic a décidé de minimiser le nombre de modifications. Calculez le nombre minimum de modifications nécessaires pour transformer la montagne dessinée par ibasic en une belle montagne.
Entrée
La première ligne contient un entier $N$. $(2 \le N \le 10^6)$
La deuxième ligne contient $N+1$ entiers $h_0, h_1, \ldots, h_N$ séparés par des espaces, représentant la montagne. $(0 \le h_i \le 10^9;$ $h_0 = h_N = 0)$
Sortie
La première ligne doit afficher le nombre minimum de modifications nécessaires pour transformer la montagne dessinée par ibasic en une belle montagne. Si, peu importe les modifications, il est impossible de transformer la montagne en une belle montagne, affichez -1.
Exemples
Entrée 1
4 0 3 2 4 0
Sortie 1
3
Entrée 2
5 0 3 2 5 9 0
Sortie 2
-1