该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Background

Special for beginners, ^_^

Description

睿爸小学有 $N(\le2\times10^5)$ 名小学生在操场上排成一排，每个人胸前有一块号码布，上面的数字都是 0 ，每次你可以选择一名小朋友，把他胸前号码布上的数字改为他左边相邻小朋友胸前号码布上的数字加一。

问最少多少次该共，可以使得小朋友胸前的号码布上的数字呈现一个指定的数组。如果不可行，输出 -1 。

Format

Input

第一行一个正整数 $N$ ，表示小朋友的数量。

后面 $N$ 行，每行一个正整数，按照从左到右的顺序给出小朋友胸前的号码布上的最终期望的目标数字。

Output

输出最少操作次数。

Samples

4
0
1
2
3

3

Limitation

1s, 1024KiB for each test case.