Daily Temperatures

You are given a list of daily temperatures over n days. For each day, determine how many days you have to wait until a warmer temperature. If there is no future day with a warmer temperature, output 0 for that day.

More formally, given an array \(T[0 \ldots n-1]\), produce an array \(answer[0 \ldots n-1]\) such that:

[ answer[i] = \begin{cases} i - j, & \text{if } j \text{ is the smallest index greater than } i \text{ with } T[j] > T[i] \ 0, & \text{if no such } j \text{ exists} \end{cases} ]

For example, if the input temperatures are [73, 74, 75, 71, 69, 72, 76, 73], the output should be [1, 1, 4, 2, 1, 1, 0, 0] because:

• Day 0: 73 is followed by 74 which is warmer, so the answer is 1.
• Day 1: 74 is followed by 75 which is warmer, so the answer is 1.
• Day 2: 75 only sees a warmer 76 four days later, so the answer is 4.
• And so on.

This problem tests your ability to efficiently process arrays and implement a stack-based solution to achieve an optimal time complexity.

inputFormat

The first line contains an integer n (1 ≤ n ≤ 10⁵), denoting the number of days.

The second line contains n space-separated integers representing the daily temperatures.

outputFormat

Output a single line containing n space-separated integers, where the i-th integer is the number of days until a warmer temperature for day i, or 0 if no such day exists.

## sample

8
73 74 75 71 69 72 76 73

1 1 4 2 1 1 0 0