////////////////////////////////maximum area of good subarray


class Solution {
public:
    int maximumScore(vector<int>& a, int k)
    {
      //so here what we are  doing is basically is
        //intuition -> each element can be  minima at some point
        //considering minima as each element and finding its left and right
        //extreme points where it is lying basically.
        int n=a.size();
        stack<pair<int,int>> stk;
        vector<int> width(n);
        for(int i=(n-1);i>=0;i--)
        {
            //for each a[i] we have to find a x in right to a[i]
            //which is just smaller than a[i], because then a[i] will be
            // minima from i to x-1;
            while(stk.size()>0&&stk.top().first>=a[i]) stk.pop();
            if(stk.empty())
            {
                width[i]=(n-1);//no element present in right smaller than i
                //so ithe element is minima from (i to (n-1))
            }
            else
            {
                //currently at smaller element than a[i];
                width[i]=stk.top().second-1;
            }
            stk.push(make_pair(a[i],i));
        }
        while(!stk.empty()) stk.pop();
        for(int i=0;i<=(n-1);i++)
        {
            while(stk.size()>0&&stk.top().first>=a[i]) stk.pop();
            if(stk.empty())
            {
                int left=0,right=width[i];//is is minima from (i to 0)
                if(left<=k&&k<=right) width[i]=(right-left+1);
                else width[i]=0;
            }
            else
            {
               int left=stk.top().second+1,right=width[i];
                //is is minima from (i to left)
               if(left<=k&&k<=right) width[i]=(right-left+1);
               else width[i]=0;
            }
            stk.push(make_pair(a[i],i));
        }
        int ans=-1;
        for(int i=0;i<=(n-1);i++) ans=max(ans,(a[i]*width[i]));
        return ans;
    }
};



////////////////////////////////////////////////////sort a stack using recursion
void SortedStack :: sort()
{
   //Your code here
   //this has access to stack and you have to just sort it
   //top to bottom like
   //11 2 32 3 41
   if(s.size()==1||s.size()==0) return;
   int temp=s.top(); s.pop();
   sort();
   if(temp>=s.top()){
       s.push(temp); return;
   }
   int temp2=s.top(); s.pop();
   s.push(temp);
   sort();
   s.push(temp2);
}



///////////////////////////////////reverse a stack through recursion

class Solution{
public:
    void insertatend(stack<int>& s,int ele){
        if(s.size()==0){
            s.push(ele); return;
        }

        int temp=s.top(); s.pop();
        insertatend(s,ele);
        s.push(temp);
    }

    void reverse(stack<int> &s){
        if(s.size()==1) return;

        int temp=s.top(); s.pop();
        reverse(s);
        insertatend(s,temp);
    }

    vector<int> Reverse(stack<int> st){
        // 1      4
        // 2      3
        // 3      2
        // 4......1
        int n=st.size(),i;
        vector<int> ans(n,0);
        if(st.size()==0) return ans;
        reverse(st);
        i=(n-1);
         while(!st.empty()){
            ans[i]=st.top(); i--; st.pop();
        }

        return ans;
    }
};