MAXI  Get higher and higher
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).
hide comments
Rishav Goyal:
20160821 19:04:22
can we solve better than n^2? any O(n) solution.


ROHIT GUPTA:
20160227 07:47:27
very nice problem. can be solved using stack 

kejriwal:
20160217 05:40:09
weak test data :P ...


ashutg19:
20160215 17:15:27
i am able to run code on my machine for number of cases,also able to run on Ideone.com,but getting wrong answer.


wisfaq:
20160215 10:27:38
@ wano:


wano:
20160213 22:40:21
Last edit: 20160227 09:08:45 

ROHIT GUPTA:
20160211 15:08:04
any hint to solve it in O(n)???? 

Seshadri R:
20160211 13:05:40
What is the constraint on height? Is it in thousands, millions or billions?


hannah:
20160210 13:27:51
I got it O(n) :) 

Î˜:
20160210 13:24:41
FWT, FTW 
Added by:  likecs 
Date:  20160207 
Time limit:  0.209s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 GOSU JSMONKEY 
Resource:  Own problem 