Daily Temperatures

You are given a sequence of daily temperatures. Your task is to figure out for each day how many days you would have to wait until a warmer temperature occurs. If there is no future day for which this is possible, enter 0 for that day.

More formally, given an integer ( n ) and a list of ( n ) temperatures ( T[0], T[1], \ldots, T[n-1] ), construct an array ( answer ) such that for each index ( i ), ( answer[i] ) is the smallest positive integer ( d ) with ( T[i+d] > T[i] ) or ( 0 ) if no such ( d ) exists.

The expected time complexity is ( O(n) ) using a monotonic stack.

inputFormat

The first line contains an integer ( n ) (1 ( \leq n \leq 10^5 )), which denotes the number of days. The second line contains ( n ) space-separated integers representing the temperatures for each day.

outputFormat

Output a single line containing ( n ) space-separated integers. The ( i^{th} ) integer represents the number of days you have to wait until a warmer temperature. If there is no warmer temperature in the future, output 0 for that day.## sample

8
73 74 75 71 69 72 76 73

1 1 4 2 1 1 0 0