SPOJ.com - Problem MAXI

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 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).

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).

Submit solution!

Added by:	likecs
Date:	2016-02-07
Time limit:	0.209s
Source limit:	50000B
Memory limit:	1536MB
Cluster:	Cube (Intel G860)
Languages:	All except: ASM64 GOSU JS-MONKEY
Resource:	Own problem

hide comments



2016-08-21 19:04:22 Rishav Goyal can we solve better than n^2? any O(n) solution. Edit: Oh! i did in O(n) only. Last edit: 2016-08-21 19:32:39
2016-02-27 07:47:27 ROHIT GUPTA very nice problem. can be solved using stack
2016-02-17 05:40:09 kejriwal weak test data :P ... my first AC code was failing on 3 3 3 3 PS : the hill station is Kullu MANALI Last edit: 2016-02-17 05:40:41*
2016-02-15 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. Dont know why this is happening? Need your help guys,this is first problem i am trying to solve on Spoj. <snip> Last edit: 2022-09-10 13:52:51
2016-02-15 10:27:38 wisfaq @ wano: Better check your keyboard as it doesn't seem to work properly. Why are you shouting in CAPITALS?
2016-02-11 15:08:04 ROHIT GUPTA any hint to solve it in O(n)????
2016-02-11 13:05:40 Seshadri R What is the constraint on height? Is it in thousands, millions or billions? REPLY-> height <= 10^9 Last edit: 2016-02-12 13:59:24
2016-02-10 13:27:51 I got it O(n) :)
2016-02-10 13:24:41 Î˜ FWT, FTW
2016-02-09 15:11:19 Any idea better than O(n^2) ?