ibasic nie jest zadowolony z góry Gwangdeoksan, na której znajduje się szkoła Dimigo, więc postanowił narysować nową górę.

Góra narysowana przez ibasica może być przedstawiona jako $N+1$ punktów na płaszczyźnie dwuwymiarowej: $(0, h_0), (1, h_1), \ldots, (N, h_N)$. Wszystkie $h_i$ są nieujemnymi liczbami całkowitymi, przy czym $h_0 = h_N = 0$.

ibasic chce, aby jego góra stała się piękną górą. Piękna góra to taka, w której dla każdego $i$ spełniającego $1 \le i \le N$ zachodzi $|h_i - h_{i-1}| = 1$.

Aby uczynić swoją górę piękną, ibasic może modyfikować rysunek w następujący sposób:

• Wybrać dwie liczby całkowite $l$ oraz $r$ takie, że $1 \le l \le r \le N-1$, i dodać $1$ do $h_l, h_{l+1}, \ldots, h_{r}$.
• Wybrać dwie liczby całkowite $l$ oraz $r$ takie, że $1 \le l \le r \le N-1$, i odjąć $1$ od $h_l, h_{l+1}, \ldots, h_{r}$.

Ponieważ rysunek nie może zostać zniszczony, po każdej modyfikacji wszystkie $h_i$ muszą pozostać nieujemne.

Modyfikowanie rysunku jest dość uciążliwe, więc ibasic postanowił wykonać minimalną liczbę operacji. Oblicz, jaka jest minimalna liczba modyfikacji potrzebna, aby góra narysowana przez ibasica stała się piękną górą.

Wejście

W pierwszej linii podano liczbę całkowitą $N$ $(2 \le N \le 10^6)$.

W drugiej linii podano $N+1$ liczb całkowitych $h_0, h_1, \ldots, h_N$ oddzielonych spacjami, reprezentujących górę $(0 \le h_i \le 10^9; h_0 = h_N = 0)$.

Wyjście

W pierwszej linii wypisz minimalną liczbę modyfikacji potrzebną, aby góra narysowana przez ibasica stała się piękną górą. Jeśli nie da się przekształcić góry w piękną górę za pomocą żadnej liczby operacji, wypisz -1.

Przykład

Wejście 1

4
0 3 2 4 0

Wyjście 1

3

Wejście 2

5
0 3 2 5 9 0

Wyjście 2

-1