Daily Temperatures

You are given a list of daily temperatures. For each day, your task is to determine 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.

More formally, given an array of temperatures \(T[0 \dots n-1]\), for each day \(i\), find the smallest index \(j\) such that \(j > i\) and \(T[j] > T[i]\). Then the answer for day \(i\) is \(j-i\). If no such \(j\) exists, the answer is \(0\).

inputFormat

The input consists of two lines:

• The first line contains an integer \(n\) (\(1 \leq n \leq 10^5\)), 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 corresponds to the number of days after day \(i\) until a warmer temperature occurs. If there is no warmer day, output 0 for that day.

8
73 74 75 71 69 72 76 73

1 1 4 2 1 1 0 0