Daily Temperatures

Problem statement

A weather application wants to annotate each day with how long a resident must wait for a warmer day. A day with the same temperature is not warmer, even when it occurs immediately afterward. Your task For every temperature, return the number of days until the next strictly higher temperature. Return zero when no later day is warmer. Important details Answers are distances in indices, not the future temperatures themselves. Examine only days after the current day. Use a monotonic stack to avoid scanning the entire remaining forecast for every position. Worked example For [30, 40, 35, 50], the waits are [1, 2, 1, 0]. Day 1 must wait past the cooler day 2 to reach day 3.

Input format

The first line contains n. The next line contains n space-separated integers; for n = 0 this line may be empty.

Output format

Print the resulting values in order, separated by spaces. Print EMPTY if there are no values.

Constraints

1 <= n <= 100000; 30 <= temperatures <= 100.

Sample input

4
30 40 35 50

Sample output

1 2 1 0