Challenge: Next Greater Number

Lab C++ Intermediate 20 points

For each of n numbers, print the next number to its right that is bigger, or -1. Use a monotonic stack.

Input

Line 1: n. Line 2: n whole numbers.

Output

The answers separated by spaces.

Example

Input

4
4 5 2 25

Output

5 25 25 -1

Sample input available Sample output available

Editor

C++

Hints

Stack of indexes still waiting.

A bigger number answers and pops everything smaller on top.

Solution explanation

Each index is pushed and popped once: O(n).

Show solution

#include <iostream>
#include <stack>
#include <vector>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> a(n), ans(n, -1);
    for (int& x : a) cin >> x;
    stack<int> s;
    for (int i = 0; i < n; i++) {
        while (!s.empty() && a[s.top()] < a[i]) {
            ans[s.top()] = a[i];
            s.pop();
        }
        s.push(i);
    }
    for (int i = 0; i < n; i++) cout << ans[i] << (i + 1 < n ? " " : "\n");
    return 0;
}

Output

Answer