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.

Constraints:

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).