There are N people who want to donate blood. Each person has a unique health level Hi. Instead of attending to each person one by one, the blood bank thought of a new way to make the whole process of blood donation faster.
Consider all people standing in a line from left to right. People will be divided in groups. Initially there is only one group with all people in it. Every second, person with the highest health level in each group will leave the group, donate blood and go home.
After a person leaves a group, all the people to the left of him in the same group (if any) form another group and all the people to the right of him in the same group (if any) form another group.
For each second, until at least one person remains, you need to tell the sum of health levels of all people that donated blood.
Input:
First line of input contains an integer N, denoting the number of people who want to donate blood. Next line contains N space separated integers Hi, denoting the health level of each person.
Output:
Print X integers, each on a new line, where X is the maximum time till which there is at least one person who hasn't gone home. ith integer represents the sum of health level of all persons who donated blood in the ith second.
Constraints:
1≤N≤3×105
1≤Hi≤109
1st second: 2nd person leaves. Sum = 5.
2nd second: 1st person and 3rd person leave. Sum = 7.
3rd second: 4th person leaves. Sum = 2.
4th second: 5th person leaves. Sum = 1.