Richard의 N마리 고양이 (1 \leq N \leq 5 \cdot 10^5)가 원형으로 줄 서 있다. i번째 고양이는 용량이 a_i (1 \leq a_i \leq 10^9) 리터인 버킷을 가지고 있으며, 모든 버킷은 처음에 가득 차 있다.

매 분마다 i번째 고양이는 1 \leq i < N일 때 자신이 가진 모든 우유를 i+1번째 고양이에게 전달하고, N번째 고양이는 1번째 고양이에게 우유를 전달한다. 모든 교환은 동시에 이루어진다(예: 한 고양이가 우유를 x 리터 보내고 x 리터를 받으면, 우유의 양은 변하지 않는다). 만약 어떤 고양이의 총 우유 양이 버킷 용량 a_i를 초과하면, 초과된 우유는 손실된다.

각 1, 2, \dots, N분 후에 남아 있는 모든 고양이의 우유 총량을 계산하라.

#8147 upload - done - how_to_reg - call_split Subtask

고양이 우유 교환 timer 1s memory 1024MB

#8147
Subtask

고양이 우유 교환 1s 1024MB