Trao Đổi Sữa (Gold)

Nong dan John co $N$ con bo xep thanh vong tron, moi con co xo dung tich $a_i$ lit, ban dau day sua. Moi phut, moi con bo chuyen toan bo sua cua minh sang con bo ke tiep (bo $i$ chuyen sang bo $i+1$, bo $N$ chuyen sang bo $1$). Tat ca cac lan chuyen xay ra dong thoi. Neu luong sua nhan vuot qua dung tich xo, phan du bi mat.

Hay in tong luong sua con lai sau moi phut, tu phut 1 den phut $N$.

Du lieu vao

• Dong 1: So nguyen $N$.
• Dong 2: $N$ so nguyen $a_1,a_2,\dots ,a_N$.

Du lieu ra

• $N$ dong, dong thu $t$ la tong luong sua sau $t$ phut.

Rang buoc

• $1\le N\le 5\times {10}^5$
• $1\le a_i\le {10}^9$

Vi du