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 socola mua ở mỗi loại ~j~ ~(1 \le j < i)~ phải thỏa mãn 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 socola loại ~j~ ít hơn loại ~i~.

Ví dụ: Số lượng socola mà cửa hàng có của các loại từ ~1~ đến ~N~ là ~[6, 5, 4, 2, 5]~.

Khi đó, mảng ~x = [0, 0, 1, 2, 5]~ là một cách mua hợp lệ (số lượng socola mua ở 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.

Dữ liệu

• 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ứa ~N~ số nguyên ~a_i~ ~(1 \le a_i \le 10^9)~ là số socola của mỗi loại.

Kết quả

• 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 Output 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~.