Days Until Warmer Temperature

Given a series of daily temperatures, determine, for each day, how many days you must wait until a warmer temperature occurs. If there is no future day for which this is possible, output 0.

Let \(T_i\) denote the temperature on the \(i\text{-th}\) day. For each day \(i\), you should compute the smallest \(j\) (with \(j > i\)) such that \(T_j > T_i\), and then the answer for day \(i\) is \(j-i\). If no such \(j\) exists, the answer is 0.

Your solution should ideally run in \(O(n)\) time.

inputFormat

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

outputFormat

Output a single line containing \(n\) space-separated integers. The \(i\text{-th}\) integer should represent the number of days to wait until a warmer temperature for the \(i\text{-th}\) day. If no such day exists, output 0 for that day.

## sample

8
73 74 75 71 69 72 76 73

1 1 4 2 1 1 0 0

</p>