Hours until a slower response

Scenario

An on-call dashboard stores one number for each hour: how many milliseconds the slowest 1% of requests took. The engineer on call wants to know, for each hour, how long the service stays at least that fast.

For each hour, they need the number of hours until the next hour that is strictly slower. If no later hour is slower, the answer is 0. A dashboard can cover up to 100,000 hours.

Your task

Write hours_until_slower(latencies).

latencies is a list of whole numbers, one for each hour, in order. Hour 0 is the oldest.
For each hour i, find the first later hour with a strictly larger value, and let j be its position. The answer for hour i is j - i. If there is no such hour, the answer is 0.
Return the list of answers, one for each hour, in order.

Examples

Example 1 (traced)#

text2 lines

Input:  latencies = [310, 340, 380, 290, 260, 300, 400, 330]
Output: [1, 1, 4, 2, 1, 1, 0, 0]

Hour read	Value	Hours popped (and their answers)	Waiting stack after (hours)
0	310	none	0
1	340	hour 0: answer 1	1
2	380	hour 1: answer 1	2
3	290	none	2, 3
4	260	none	2, 3, 4
5	300	hour 4: answer 1, hour 3: answer 2	2, 5
6	400	hour 5: answer 1, hour 2: answer 4	6
7	330	none	6, 7

Hours 6 and 7 are still waiting at the end, so their answers stay 0.

Example 2#

text2 lines

Input:  latencies = [200, 200, 300]
Output: [2, 1, 0]

Equal is not slower. Hour 0 waits past hour 1, which is also 200, until hour 2.

Example 3#

text2 lines

Input:  latencies = [500, 400, 300, 200]
Output: [0, 0, 0, 0]

Every hour is faster than the one before, so no hour ever finds a slower one.

Constraints

1 ≤ number of hours ≤ 10^5
1 ≤ each latency ≤ 10^5

What does n ≤ 10^5 tell you?

A plan that scans forward from every hour costs up to n^2 / 2 steps: 5 × 10^9 when the latencies fall all the way down. That is too slow.

So the work must be close to n steps in all. Each hour should be handled a constant number of times, even though its answer depends on hours far to its right.

Scenario

For each hour, they need the number of hours until the next hour that is strictly slower. If no later hour is slower, the answer is 0. A dashboard can cover up to 100,000 hours.

Your task

Write hours_until_slower(latencies).

latencies is a list of whole numbers, one for each hour, in order. Hour 0 is the oldest.
For each hour i, find the first later hour with a strictly larger value, and let j be its position. The answer for hour i is j - i. If there is no such hour, the answer is 0.
Return the list of answers, one for each hour, in order.

Examples

Example 1 (traced)#

text2 lines

Input:  latencies = [310, 340, 380, 290, 260, 300, 400, 330]
Output: [1, 1, 4, 2, 1, 1, 0, 0]

Hour read	Value	Hours popped (and their answers)	Waiting stack after (hours)
0	310	none	0
1	340	hour 0: answer 1	1
2	380	hour 1: answer 1	2
3	290	none	2, 3
4	260	none	2, 3, 4
5	300	hour 4: answer 1, hour 3: answer 2	2, 5
6	400	hour 5: answer 1, hour 2: answer 4	6
7	330	none	6, 7

Hours 6 and 7 are still waiting at the end, so their answers stay 0.

Example 2#

text2 lines

Input:  latencies = [200, 200, 300]
Output: [2, 1, 0]

Equal is not slower. Hour 0 waits past hour 1, which is also 200, until hour 2.

Example 3#

text2 lines

Input:  latencies = [500, 400, 300, 200]
Output: [0, 0, 0, 0]

Every hour is faster than the one before, so no hour ever finds a slower one.

Constraints

1 ≤ number of hours ≤ 10^5
1 ≤ each latency ≤ 10^5

What does n ≤ 10^5 tell you?

A plan that scans forward from every hour costs up to n^2 / 2 steps: 5 × 10^9 when the latencies fall all the way down. That is too slow.

So the work must be close to n steps in all. Each hour should be handled a constant number of times, even though its answer depends on hours far to its right.