Question

Days to Wait for a Warmer Temperature

You are given an array of daily temperatures. For each day, your task is to determine how many days you have to wait until a warmer temperature occurs. If there is no future day for which this is possible, output KaTeX can only parse string typed expression for that day.

Input

The first line contains a single integer KaTeX can only parse string typed expression — the number of days.
The second line contains KaTeX can only parse string typed expression integers representing the daily temperatures — KaTeX can only parse string typed expression.

Output

Print KaTeX can only parse string typed expression integers where the KaTeX can only parse string typed expression-th integer represents the number of days you must wait after day KaTeX can only parse string typed expression to get a warmer temperature. If no such day exists, print KaTeX can only parse string typed expression.

Example

Input
8
73 74 75 71 69 72 76 73

Output
1 1 4 2 1 1 -1 -1

Explanation
Day 0 (73) → warmer temperature on day 1 (74), wait 1 day
Day 1 (74) → warmer temperature on day 2 (75), wait 1 day
Day 2 (75) → warmer temperature on day 6 (76), wait 4 days
Day 3 (71) → warmer temperature on day 5 (72), wait 2 days
Day 4 (69) → warmer temperature on day 5 (72), wait 1 day
Day 5 (72) → warmer temperature on day 6 (76), wait 1 day
Day 6 (76) → no warmer future day → -1
Day 7 (73) → no warmer future day → -1

Online

Explore Newton School

Recent Questions

Most Solved Questions

Least Solved Questions