Daily Temperatures

Given a sequence of daily temperatures, compute for each day the number of days until a warmer temperature occurs. More formally, for each index \(i\) (0-indexed), determine the smallest integer \(k\) such that \(T[i+k] > T[i]\). If no such \(k\) exists, output 0 for that day. The relationship can be expressed in LaTeX as: $$\text{answer}[i] = \min\{k \mid k > 0 \text{ and } T_{i+k} > T_i\}$$ with the convention that if the set is empty, then \(\text{answer}[i] = 0\>.

inputFormat

The first line of input contains a single integer \(n\), the number of days. The second line contains \(n\) space-separated integers representing the daily temperatures.

outputFormat

Output a single line with \(n\) space-separated integers, where the \(i\)th integer corresponds to the number of days one must wait until a warmer temperature. If no such day exists, output 0.

8
30 40 50 60 70 80 90 100

1 1 1 1 1 1 1 0