Bajtazar is going on a sightseeing bicycle trip around Byteland. He is now wondering which useful items to pack into his backpack for the journey. Unfortunately, he has very little time, so he has arranged the potential items in a sequence from most important to least important. His procedure is very simple: he considers the items one by one, and each item is taken on the trip as long as it does not exceed the backpack's capacity (of course, counting the weight of items already packed).

The key question remains: which backpack should he take on the trip? Bajtazar suspects that he will manage on the trip if he takes at least $k$ items. Unfortunately, our hero is not yet sure what the exact value of the parameter $k$ is. In such a situation, what is the minimum backpack capacity required for each possible value of $k$?

Input

The first line of input contains a single natural number $n$ ($1 \le n \le 500\,000$) representing the number of potential items Bajtazar is considering taking on the trip. The second line of input contains a sequence of $n$ natural numbers $w_1, w_2, \dots, w_n$ ($1 \le w_i \le 10^9$) separated by single spaces. These are the masses of the items in the order they are considered by Bajtazar.

Output

The first and only line of output should contain $n$ integers separated by single spaces: the $k$-th number should represent the minimum backpack capacity that guarantees Bajtazar will take at least $k$ items with him.

Examples

Input 1

6
10 8 3 30 5 10

Output 1

3 13 21 26 36 66

Note

The second output number is 13. If the backpack capacity is 13, Bajtazar will take the first item (with mass 10), will not take the second item (because he only has 3 of remaining capacity left, and the item weighs 8), and will take the item with mass 3. In total, he will take exactly the required two items.

Subtasks