Hôm nay Lộc muốn ăn socola nên đã đến cửa hàng để mua. Cửa hàng bán $N$ loại socola khác nhau. Loại thứ $i$ có $a_i$ viên socola có thể bán.

Lộc là thiếu gia tiền nhiều vô kể. Vì thế Lộc không bị giới hạn bởi bất kỳ giá tiền nào và muốn mua nhiều socola nhất có thể. Tuy nhiên, nếu Lộc mua $x_i$ socola loại $i$ $(0\le$ $x_i$ $\le a_i)$ thì số lượng mua socola các loại $j$ từ $1$ đến $i$ - $1$ $(1\le j<i)$ phải thỏa một trong hai điều kiện:

• $x_j=0$. Lộc không mua socola loại j.

• $x_j<x_i$. Lộc mua được ít socola loại j hơn loại i.

Ví dụ: Cửa hàng trưng bán số lượng socola các loại từ 1 đến N là: [6, 5, 4, 2, 5]

Mảng x = [0, 0, 1, 2, 5] là số lượng mua được socola các loại từ 1 đến N.

Bạn hãy tính số socola tối đa mà Lộc mua được ở cửa hàng.

Input

• Dòng đầu chứa số nguyên $N$ $(1\le N\le 2\times {10}^5)$ là số loại socola.

• Dòng tiếp theo chứ $N$ số nguyên $a_i$ $(1\le a_i\le {10}^9)$ là số socola của mỗi loại.

Ouput

• In ra số socola tối đa mà Lộc có thể mua.

Ví dụ

Sample Input 1

5

1 2 1 3 6

Sample Ouput 1

10

Sample Input 2

5

3 2 5 4 10

Sample Output 2

20

Sample Input 3

4

1 1 1 1

Sample Output 3

1

Giải thích

Ví dụ 1: Số socola tối đa mua được là: 0 + 0 + 1 + 3 + 6 = 10.

Ví dụ 2: Số socola tối đa mua được là: 1 + 2 + 3 + 4 + 10 = 20.

Ví dụ 3: Số socola tối đa mua được là: 0 + 0 + 0 + 1 = 1.