For each day, how many days until a strictly warmer day? If none comes, the answer is 0.
Input
The first line has n (1 ≤ n ≤ 10⁵). The second line has the n temperatures (integers).
Output
The n answers, separated by spaces.
Examples
Example 1 · Input
8 73 74 75 71 69 72 76 73
Expected output
1 1 4 2 1 1 0 0
Example 2 · Input
3 30 30 30
Expected output
0 0 0
Prompts inside input() are ignored when checking, so input("n: ") is fine.
Hints
Hint 1
Keep a stack of the days still waiting for a warmer day.
Hint 2
Each new day pops every waiting day that is colder, and answers it.
Hint 3
Days never answered get 0.
Solution
Show one correct solution (try it yourself first)
n = int(input())
temps = list(map(int, input().split()))
answer = [0] * n
waiting = []
for day, t in enumerate(temps):
while waiting and temps[waiting[-1]] < t:
cold = waiting.pop()
answer[cold] = day - cold
waiting.append(day)
print(*answer)