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 seperated 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.
Sample Input :
4
2 1 4 4
Sample Outout :
5 6 12 10
Constraints :
1 <= M <= 100000
1 <= h_i <= 10000
hide comments
bartol3141:
20180205 12:41:42
Very good problem!!! Worth solving. 

:D:
20160819 13:32:22
On output number size. Just analyze the biggest possible test case: M = 10^5, h_i = 10^4 for all i. 

Jose Sanchez:
20121229 01:14:26
Do the output integers fits in a c++ int(4 bytes)? Last edit: 20121229 01:18:12 

Raghavendran Ramachandran:
20120924 15:15:57
Nice problem! 

Daniel González:
20120321 02:39:53
what's the output specification? does it have spaces?


Rajesh patidar:
20120128 20:18:19
any special test case for the problem..?

Added by:  Varun Jalan 
Date:  20100729 
Time limit:  0.635s 
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 