Daily Temperatures

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

The expected solution should run in \(O(n)\) time complexity. For example, given the input temperatures:

73 74 75 71 69 72 76 73

The output should be:

1 1 4 2 1 1 0 0

Make sure your program reads input from stdin and writes output to stdout.

inputFormat

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

Example:

8
73 74 75 71 69 72 76 73

outputFormat

Output a single line with \(n\) space-separated integers, where each integer is the number of days until a warmer temperature. If no such day exists, output \(0\) for that day.

Example:

1 1 4 2 1 1 0 0

## sample

8
73 74 75 71 69 72 76 73

1 1 4 2 1 1 0 0