ibasic không thích ngọn núi Gwangdeok ở Dimigo, vì vậy cậu ấy quyết định vẽ một ngọn núi mới.

Ngọn núi mà ibasic vẽ có thể được biểu diễn bằng $N+1$ điểm trên mặt phẳng $2$ chiều: $(0, h_0), (1, h_1), \ldots, (N, h_N)$. Tất cả $h_i$ đều là các số nguyên không âm và $h_0 = h_N = 0$.

ibasic muốn biến ngọn núi mình vẽ thành một ngọn núi tuyệt đẹp. Một ngọn núi tuyệt đẹp là ngọn núi thỏa mãn $|h_i - h_{i-1}| = 1$ với mọi $1 \le i \le N$.

Để biến ngọn núi của mình thành ngọn núi tuyệt đẹp, ibasic có thể sửa đổi bản vẽ theo các cách sau:

• Chọn hai số nguyên $l, r$ sao cho $1 \le l \le r \le N-1$, sau đó cộng $1$ vào tất cả các giá trị $h_l, h_{l+1}, \ldots, h_{r}$.
• Chọn hai số nguyên $l, r$ sao cho $1 \le l \le r \le N-1$, sau đó trừ $1$ vào tất cả các giá trị $h_l, h_{l+1}, \ldots, h_{r}$.

Vì không muốn làm hỏng bản vẽ, sau khi sửa đổi, tất cả $h_i$ vẫn phải đảm bảo không âm ($h_i \ge 0$).

Việc sửa đổi bản vẽ khá phiền phức nên ibasic quyết định thực hiện số lần sửa đổi ít nhất có thể. Hãy tính số lần sửa đổi tối thiểu để biến ngọn núi của ibasic thành ngọn núi tuyệt đẹp.

Dữ liệu vào

Dòng đầu tiên chứa số nguyên $N$. $(2\le N\le 10^6)$

Dòng thứ hai chứa $N+1$ số nguyên $h_0, h_1, \ldots, h_N$ cách nhau bởi dấu cách, biểu diễn ngọn núi. $(0 \le h_i \le 10^9;$ $h_0 = h_N = 0)$

Dữ liệu ra

Dòng đầu tiên in ra số lần sửa đổi tối thiểu cần thiết để biến ngọn núi của ibasic thành ngọn núi tuyệt đẹp. Nếu không thể biến ngọn núi thành ngọn núi tuyệt đẹp dù có sửa đổi thế nào đi nữa, hãy in ra -1.

Ví dụ

Dữ liệu vào 1

4
0 3 2 4 0

Dữ liệu ra 1

3

Dữ liệu vào 2

5
0 3 2 5 9 0

Dữ liệu ra 2

-1