Daily Temperatures

Source: LeetCode

Version: Phuoc Hung OJ Extended

Problem Statement

Given an array temperatures, where the $i$-th element is the temperature on day $i$, determine for each day how many days must pass before a warmer temperature occurs. If no warmer day occurs later, the answer is $0$.

Input

The first line contains $n$, the number of days. The second line contains the $n$ temperatures.

Output

Print $n$ integers. The $i$-th integer is the number of days from day $i$ to the next warmer day, or $0$.

Subtasks

• Subtask 1 (30 points): $n\le2000$; all other conditions are unchanged.
• Subtask 2 (70 points): $1\le n\le10^5$, $30\le temperatures_i\le100$.

Examples

Input

8
73 74 75 71 69 72 76 73

Output

1 1 4 2 1 1 0 0

Explanation

The daily temperatures are $73,74,75,71,69,72,76,73$.

• Day $1$ is $73$; day $2$ is $74>73$, so the wait is $1$ day.
• Day $2$ is $74$; day $3$ is $75>74$, so the wait is $1$ day.
• Day $3$ is $75$; days $4,5,6$ are $71,69,72$, none warmer than $75$; day $7$ is $76>75$, so the wait is $7-3=4$ days.
• Day $4$ is $71$; day $5$ is $69$, while day $6$ is $72>71$, so the wait is $2$ days.
• Day $5$ is $69$; day $6$ is $72>69$, so the wait is $1$ day.
• Day $6$ is $72$; day $7$ is $76>72$, so the wait is $1$ day.
• Day $7$ is $76$ and no later day is warmer, so its answer is $0$.
• Day $8$ is the final day, so its answer is $0$.

Hence the output is 1 1 4 2 1 1 0 0.