How long this price has been the best

Medium

2000 ms limit256 MB memoryStacks and queues Arrays

Stuck?

Show a hint

The span ends at the most recent strictly higher price. Keep a stack of days that could still block a later day, and drop any that today outranks.

The ideas behind this problem

Monotonic stacks: the nearest bigger thing, in one pass Stacks and queues: choosing which end to work from

Next in this lesson

The biggest rectangle inside a histogram

A share price is quoted once a day. The span on a given day is the number of consecutive days ending that day, today included, on which the price was less than or equal to today's price.

Report the span for every day.

Worked example#

For [100, 80, 60, 70, 60, 75, 85]:

day	price	days counted back	span
0	100	itself only	1
1	80	itself only, 100 is higher	1
2	60	itself only, 80 is higher	1
3	70	70 and 60	2
4	60	itself only	1
5	75	75, 60, 70, 60	4
6	85	85, 75, 60, 70, 60, 80	6

So the answer is [1, 1, 1, 2, 1, 4, 6].

The idea#

The span stops at the most recent day with a strictly higher price. Nothing before that day can be counted, because that day blocks the run. So the real question for each day is: where is the previous higher price?

Counting backwards day by day is a nested loop. Instead keep a stack of days whose prices are still higher than everything after them. When today arrives, pop every day priced at or below today, because none of them can ever block a later day again: today is higher and stands in front of them.

Whatever is left on top is the previous higher day, and the span is the distance to it. If the stack empties, no day has been higher, so the span reaches back to the very first day.

Each day is pushed once and popped once, so this is one pass however the prices move.

Constraints#

1 <= n <= 100000
1 <= prices[i] <= 1000000

Input

prices is a count then that many integers.

Output

A count is not printed. Print the spans, separated by spaces.

Examples

Input

7
100 80 60 70 60 75 85

Output

1 1 1 2 1 4 6

Day 6 at 85 reaches back past everything except the opening 100.

Input

4
10 4 5 90

Output

1 1 2 4

90 beats every earlier price, so its span is the whole run.

Input

3
5 5 5

Output

1 2 3

Equal prices still count, because the rule is less than or equal.

Something wrong with this problem? Report an issue

Ready to try it

Write your solution in C, C++, Java or Python and see every test case come back with the time and memory it took.

Create a free account Sign in

Free, and it stays free. No card.