The Next Big Thing Solution

Problem

Given an array A of N distinct integers. For each element find the first element coming after it, ,which is strictly greater than it i.e for each element Ai find the first element in the range [i+1, N] which is greater than Ai if it exists, else print -1. Print an space separated array of size N representing Next Big Thing for each element.

Input

• First line contain an integer N denoting the size of array.
• Second line contains N space separated integers denoting the array.

Output

A single line containing N space separated integers.

Constraints

• 1 ≤ N ≤ 106
• 1 ≤ Ai ≤ 107

Information to Score Partial Points

• For 30% of score it is guaranteed that N ≤ 1000.
• For rest 70% score , original constraints are applicable.

Example

Input:
5
2 1 6 4 5
Output:
6 6 -1 5 -1

Explanation

The next greater element of 2 will be 6 similarly for 1 the next greater element will be 6 however for 6 there is no greater element after 6 hence -1. 

Program :

 #include <bits/stdc++.h>

using namespace std;

vector<int> NGE(vector<int> v)

{    

    vector<int> nge(v.size());    

    stack<int> st;   

    for (int i = 0; i < v.size(); i++)   

    {       

        while ((!st.empty()) && (v[i] > v[st.top()]))   

        {           

            nge[st.top()] = i;         

            st.pop();     

            }    

            st.push(i);  

            }   

            while (!st.empty())  

            {       

                nge[st.top()] = -1;    

                st.pop(); 

                } 

                return nge;

    

}

int main()

{

    int n, i;

    cin >> n;    

    vector<int> vect;   

    for (int i = 0; i < n; i++)   

    {       

        int x;       

        cin >> x;       

        vect.push_back(x);    

    }    

    vector<int> nge = NGE(vect);   

    for (i = 0; i < n; i++)       

    cout << ((nge[i] == (-1)) ? -1 : vect[nge[i]]) << " ";

}