A certain city has M buildings, all having a width of 1. The ith building has height h_i units. The outline of the city can be seen by everyone passing along, and you wish to place an advertisement in front. You want the advertisement to be totally contained within the boundary defined by the outline of the city. The advertisement should be rectangular in shape, and its base should be at ground level. Also, it should have an integral height and its vertical edges should coincide with the vertical edges of the buildings. Now you wonder, for each building x, how many ways are there to place an advertisement such that it hides (fully or partially) building x?

Input

The first line contains an integer M, the number of buildings. The second line contains M space separated integers, the heights of the buildings.

Output

Output M integers. The ith integer is the number of possible advertisements which cover the ith building partially or fully.

Example

Input:
4
2 1 4 4

Output:
5 6 12 10

Constraints

1 <= M <= 100000

1 <= h_i <= 10000