Challenge: Wait for a Warmer Day

Lab Java Intermediate 20 points

For each day's temperature, print how many days you must wait for a warmer day (strictly higher). Print 0 if no warmer day comes. Use a monotonic stack of day indexes – O(n), not O(n²).

Input

Line 1: n. Line 2: n temperatures.

Output

n numbers separated by spaces.

Example

Input

8
73 74 75 71 69 72 76 73

Output

1 1 4 2 1 1 0 0

Sample input available Sample output available

Editor

Java

Hints

Keep a stack of days that haven't found a warmer day yet.

When today is warmer than the day on top, pop it: its answer is today - thatDay.

Solution explanation

Every day is pushed once and popped at most once: O(n).

Show solution

import java.util.ArrayDeque;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] t = new int[n];
        for (int i = 0; i < n; i++) t[i] = sc.nextInt();
        int[] wait = new int[n];
        ArrayDeque<Integer> stack = new ArrayDeque<Integer>();
        for (int i = 0; i < n; i++) {
            while (!stack.isEmpty() && t[stack.peek()] < t[i]) {
                int day = stack.pop();
                wait[day] = i - day;
            }
            stack.push(i);
        }
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < n; i++) sb.append(i > 0 ? " " : "").append(wait[i]);
        System.out.println(sb);
    }
}

Output

Answer