Daily Temperatures

Given a list of daily temperatures, your task is to determine for each day how many days you would have to wait until a warmer temperature. If there is no future day for which this is possible, output 0 for that day.

You are required to design an efficient algorithm with an expected time complexity of \(O(n)\). The result for each day \(i\) is computed as:

$$\text{ans}[i]=\begin{cases} j-i,&\text{if }j\text{ is the first day after }i\text{ with a higher temperature},\\ 0,&\text{if no such day exists}.\end{cases}$$

inputFormat

The input is given via standard input (stdin). The first line contains an integer \(n\) representing the number of days. The second line contains \(n\) space-separated integers, each representing the temperature of a day.

outputFormat

The output should be printed to standard output (stdout) as a single line containing \(n\) space-separated integers. Each integer corresponds to the number of days until a warmer temperature for the respective day. If no warmer day exists for that day, output 0.

8
73 74 75 71 69 72 76 73

1 1 4 2 1 1 0 0