Daily Temperatures

Given a sequence of daily temperatures, determine how many days you would have to wait until a warmer temperature. For each day, if there is no future day for which this is possible, output 0.

The problem can be mathematically formulated as follows: Given an array \( T = [T_1, T_2, \dots, T_n] \), for each index \( i \) (1-based indexing), find the smallest index \( j \) such that \( j > i \) and \( T_j > T_i \). The answer for day \( i \) is \( j-i \) if such \( j \) exists, otherwise 0.

This problem requires an efficient solution. A common approach is to use a stack to keep track of indices of the days waiting for a warmer temperature.

inputFormat

The first line of input contains a single integer \( n \) (1 \( \leq n \leq 10^5\)) representing the number of days. The second line contains \( n \) space-separated integers, where each integer \( T_i \) represents the temperature on day \( i \) (\( 0 \leq T_i \leq 10^5 \)).

outputFormat

Output a single line containing \( n \) space-separated integers, where the \( i \)-th integer is the number of days you have to wait until a warmer temperature. If there is no future day with a higher temperature, output 0 for that day.

8
73 74 75 71 69 72 76 73

1 1 4 2 1 1 0 0