Daily Temperatures

Given a list of daily temperatures, your task is to compute, for each day, the number of days that must pass until a warmer temperature occurs. If no warmer temperature exists in the future, output 0 for that day.

More formally, let \( T[i] \) be the temperature on day \( i \). You need to compute an array \( D \) where:

[ D[i] = \begin{cases} j - i & \text{where } j \text{ is the smallest index greater than } i \text{ such that } T[j] > T[i], \ 0 & \text{if no such } j \text{ exists.} \end{cases} ]

Consider the following examples:

• Input: 73 74 75 71 69 72 76 73 Output: 1 1 4 2 1 1 0 0
• Input: 30 40 50 60 Output: 1 1 1 0
• Input: 30 60 90 Output: 1 1 0

Your solution should read input from stdin and print the result to stdout.

inputFormat

The first line of input contains a single integer \( n \) indicating the number of days (\( 1 \leq n \leq 10^5 \)).

The second line contains \( n \) space-separated integers representing the temperatures for each day.

outputFormat

Output a single line with \( n \) space-separated integers, where the \( i \)-th integer is the number of days you must wait after day \( i \) to get a warmer temperature, or \( 0 \) if no such day exists.

## sample

8
73 74 75 71 69 72 76 73

1 1 4 2 1 1 0 0