You are travelling to Kullu Manali, 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 segments 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).