There is a sequence X of length N, where every element is initially 0. Let Xi denote the i-th element of X.

You are given a sequence A of length N. The i-th element of A is Ai. Determine if we can make X equal to A by repeating the operation below. If we can, find the minimum number of operations required.

Choose an integer i such that 1≤ i ≤N−1. Replace the value of Xi+1 with the value of Xi plus 1.

Constraints

1≤ N ≤2×10⁵

0≤ Ai ≤10⁹(1≤ i ≤N)

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N

 A1

:

:

AN

Output

If we can make X equal to A by repeating the operation, print the minimum number of operations required. If we cannot, print −1.