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ó ai 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 xi socola loại i (0 ≤ xi ≤ ai) thì số lượng mua socola các loại j từ 1 đến i − 1 (1 ≤ j < i) phải thỏa một trong hai điều kiện:

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

• xj < xi. 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 ≤ N ≤ 2 × 10^5) là số loại socola.

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

Output

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

Sample Input

5
1 2 1 3 6

Sample Output

10

Sample Input

5
3 2 5 4 10

Sample Output

20