////////////////////////////////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);
}