Beginner Free Contest 32: https://drive.google.com/file/d/1cH1oN6-7KiDMskRP9vhnTT2eu2cQd4rK/view?usp=sharing

Lời giải: https://drive.google.com/file/d/1Y5T4kuQRkYhgJPAgbuCz0za-PxmJnLlq/view?usp=sharing

Hôm nay Lộc muốn ăn bánh chưng nên đã đến cửa hàng để mua. Cửa hàng bán N loại bánh chưng khác nhau. Loại thứ i có ~a_i~ chiếc bánh chưng 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 bánh chưng nhất có thể.

Tuy nhiên, nếu số lượng bánh chưng Lộc mua ~x_i~ bánh chưng loại i ~(0 \leq x_i \leq a_i)~ thì số lượng mua bánh chưng các loại j từ 1 đến i - 1 ~(1 \leq j < i)~ phải thỏa mãn một trong hai điều kiện:

• ~x_j~ = 0. Lộc không mua bánh chưng loại j.
• ~x_j < x_i ~ Lộc mua được ít bánh chưng loại j hơn loại i.

Ví dụ 1: Cửa hàng bán số lượng bánh chưng 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 bánh chưng mua được các loại từ 1 đến N

Ví dụ 2: Cửa hàng bán số lượng bánh chưng các loại từ 1 đến N là: [1, 999, 100000, 0, 0] Mảng x = [0, 0, 0 , 0, 0] là số lượng bánh chưng mua được các loại từ 1 đến N và là số lượng bánh chưng tối đa Lộc có thể mua. Chứ không phải là [1, 999, 100000, 0, 0], bởi vì không có bánh chưng nào ở ô cuối cùng, và đề bài có yêu cầu là tất cả ô phía trước một là bằng 0, hai là phải nhỏ hơn ô hiện tại.

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

Input

• Dòng đầu tiên gồm 1 số nguyên N ~(1 \leq N \leq 2.10^5)~, số loại bánh chưng.

• Dòng thứ hai gồm N số nguyên ~a_1, a_2, a_3 ..., a_n ~ ~ (1 \leq a_i \leq 10^9 )~ là số lượng bánh chưng mỗi loại.

Output

• In ra màn hình số bánh chưng tối đa mà Lộc có thể mua.

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ố bánh chứng tối đa mua được là: 0 + 0 + 1 + 3 + 6 = 10.

Ví dụ 2: Số bánh chứng tối đa mua được là: 1 + 2 + 3 + 4 + 10 = 20.

Ví dụ 3: Số bánh chứng tối đa mua được là: 0 + 0 + 0 + 1 = 1.