BUILDING - Buildings

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


Added by:Varun Jalan
Date:2010-07-29
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: NODEJS OBJC PERL6 VB.NET
Resource:own problem used for Indian ICPC training camp

hide comments
2018-03-16 16:11:28
VERY NICE. I LIKE
2018-02-05 12:41:42
Very good problem!!! Worth solving.
2016-08-19 13:32:22 :D
On output number size. Just analyze the biggest possible test case: M = 10^5, h_i = 10^4 for all i.
2012-12-29 01:14:26 Jose Sanchez
Do the output integers fits in a c++ int(4 bytes)?

Last edit: 2012-12-29 01:18:12
2012-09-24 15:15:57 Raghavendran Ramachandran
Nice problem!
2012-03-21 02:39:53 Daniel González
what's the output specification? does it have spaces?
The input is just one case?

Re: The numbers are to be separated by spaces.

Last edit: 2012-09-24 15:15:30
2012-01-28 20:18:19 Rajesh patidar
any special test case for the problem..?
i am getting WA.. :( , i verified the output with brutforce output also..

any suggestion..?
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.