Daily Temperatures

Given an array of integers representing daily temperatures, return an array such that for each day in the input, tells you how many days you would have to wait until a warmer temperature. If there is no future day for which this is possible, the answer is 0.

The problem can be solved efficiently using a monotonic stack that keeps track of indices of the days. When we encounter a day with a temperature higher than the temperature at the top of the stack, we have found the next warmer day for the day represented by the index at the top of the stack.

The formula for the waiting period for a day i when a warmer temperature is found at day j is given by:

$$\text{waiting}[i] = j - i$$

If no such day exists, then waiting[i]=0.

inputFormat

The first line contains an integer n indicating 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 representing the number of days to wait for a warmer temperature for each day. If no warmer 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