A ibasic no le gusta el monte Gwangdeok, donde se encuentra el Dimigo, así que ha decidido dibujar una nueva montaña.
La montaña que dibujó ibasic puede representarse mediante $N+1$ puntos en un plano bidimensional: $(0, h_0), (1, h_1), \ldots, (N, h_N)$. Todos los $h_i$ son enteros no negativos y $h_0 = h_N = 0$.
ibasic quiere convertir la montaña que dibujó en una hermosa montaña. Una hermosa montaña es aquella en la que $|h_i - h_{i-1}| = 1$ para todo $i$ tal que $1 \le i \le N$.
Para convertir su montaña en una hermosa montaña, ibasic puede modificar el dibujo de la siguiente manera:
- Elegir dos enteros $l$ y $r$ tales que $1 \le l \le r \le N-1$ y sumar $1$ a $h_l, h_{l+1}, \ldots, h_{r}$.
- Elegir dos enteros $l$ y $r$ tales que $1 \le l \le r \le N-1$ y restar $1$ a $h_l, h_{l+1}, \ldots, h_{r}$.
Como no quiere arruinar el dibujo, después de cada modificación, todos los $h_i$ deben seguir siendo mayores o iguales a $0$.
Modificar el dibujo es una tarea bastante tediosa, por lo que ibasic ha decidido realizar el número mínimo de modificaciones. Calcule el número mínimo de modificaciones necesarias para que la montaña de ibasic se convierta en una hermosa montaña.
Entrada
La primera línea contiene un entero $N$. $(2\le N\le 10^6)$
La segunda línea contiene $N+1$ enteros $h_0, h_1, \ldots, h_N$ separados por espacios, que representan la montaña. $(0 \le h_i \le 10^9;$ $h_0 = h_N = 0)$
Salida
La primera línea debe contener el número mínimo de modificaciones necesarias para convertir la montaña de ibasic en una hermosa montaña. Si no es posible convertir la montaña en una hermosa montaña sin importar cómo se realicen las modificaciones, imprima -1.
Ejemplos
Entrada 1
4 0 3 2 4 0
Salida 1
3
Entrada 2
5 0 3 2 5 9 0
Salida 2
-1