Daily Temperatures

Given a list of daily temperatures, determine for each day how many days you must wait until a warmer temperature. Formally, for each day (i), find the smallest positive integer (k) such that (T[i+k] > T[i]). If no such (k) exists, then (answer[i]=0).

This problem is a classic application of the monotonic stack technique. Input is read from standard input (stdin) and the result is printed to standard output (stdout).

inputFormat

The first line contains a single integer (n), representing 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. The (i)-th integer represents the number of days you have to wait for 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