## MAXI - Get higher and higher

no tags

You are travelling to Kullu Manili, a hill station in India. You saw some huge mountains and very curious to climb the highest ones. Assume that there are n mountains of height hi given.

But you were wondering about what could be the total height i need to climb if I climb only the mountain of maximum height only in a segment of k continuous mountains, considering all k segements possible. You want to calculate this for all k, such that 1<=k<=n.

Mathematically, we need to find the sum of maximum element in each possible continuous segment of size k.

### Input

The first line contains an input n.

Then n numbers follow, denoting the height of ith mountain.

### Output

Output n lines, where ith line contains the sum of height of mountains to climb considering all continuous segments of size i.

1<=n<=10000

### Example

```Input:
5```
```5 3 4 2 3

Output:
17```
`16`
`13`
`9`
`5`
`Explanation:`
`For k=1, all the contiguous segments are (5), (3), (4), (2), (3). The total sum of maximum in each segment is 17 (5+3+4+2+3).`
`For k=2, all the contiguous segments are (5,3), (3,4), (4,2), (2,3). The total sum of maximum in each segment is 16 (5+4+4+3).`
`For k=3, all the contiguous segments are (5,3,4), (3,4,2), (4,2,3). The total sum of maximum in each segment is 13 (5+4+4).`
`For k=4, all the contiguous segments are (5,3,4,2), (3,4,2,3). The total sum of maximum in each segment is 9 (5+4).`
`For k=5, all the contiguous segments are (5,3,4,2,3). The total sum of maximum in each segment is 5 (5).`