.
Ami sở hữu một trang trại kỳ lân. Trang trại của Ami có vô cực cái chuồng được đánh số thứ tự từ 1 và mỗi chuồng chỉ được nhốt tối đa 1 con kỳ lân. Kỳ lân là một sinh vật huyền bí, do đó tâm trạng của nó cũng tăng giảm một cách thất thường như vậy. Mỗi ngày, Ami có thể mua một con kỳ lân có tâm trạng là m. Nếu một con kì lân có tâm trạng là t được nhốt vào lồng có chỉ số i, tâm trạng của nó sẽ trở thành t*i. Ami muốn tìm cách xếp các chú kì lân sao cho tổng tâm trạng của các chú kì lân là càng nhỏ càng tốt.
Dữ liệu vào
Dòng đầu tiên là 1 số nguyên dương n (n <= 3*105) là số kì lân mà Ami mua về.
Dòng tiếp theo là n số nguyên dương ai (ai <= 3*105) là tâm trạng chú kì lân mà Ami mua ở ngày thứ i.
Dữ liệu ra
Một dòng gồm n số nguyên dương bi. Số thứ i là cách xếp các chú kì lân mua từ ngày 1 đến ngày thứ i vào các chuồng sao cho tổng tâm trạng là bé nhất.
3
1 1 1
Output
1 3 6
Giải thích
Ở ngày 1, ta xếp chú kì lân vào chuồng 1, do đó tổng tâm trạng là 1.
Ở ngày 2, ta xếp các chú kì lân vào 2 chuồng 1 và 2, do đó tổng tâm trạng là 1 + 2 = 3.
Ở ngày 2, ta xếp các chú kì lân vào 2 chuồng 1, 2 và 3, do đó tổng tâm trạng là 1 + 2 + 3 = 6.