//
//  main.cpp
//  Stock Span
//
//  Created by Himanshu on 11/09/21.
//

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



void printArray (int arr[], int n) {
    for (int i=0; i<n; i++) {
        cout<<arr[i]<<" ";
    }
    cout<<endl;
}

void solve(int S[], int arr[], int n) {
    stack<int> st;
    
    S[0] = 1;
    st.push(0);
    
    for (int i=1; i<n; i++) {
        
        while (!st.empty() && arr[st.top()] < arr[i]) {
            st.pop();
        }
        
        if (st.empty()) {
            S[i] = i + 1;
        } else {
            S[i] = i - st.top();
        }
        
        st.push(i);
    }
}

int main () {
    int n = 7;
    int arr[] = {100, 80, 60, 70, 60, 75, 85};
    int S[n];
    
    cout<<"Initail array:"<<endl;
    printArray(arr, n);

    solve (S, arr, n);
    
    cout<<"Stock Span:"<<endl;
    printArray(S, n);

    return 0;
}