#include<stack>
vector<int> nextsmallelement(vector<int> arr, int n){ // a vector containing next
stack<int> s; // small element for every index
s.push(-1);
vector<int> ans(n);
for(int i=n-1;i>=0;i--){
int curr=arr[i];
while(s.top()!= -1 && arr[s.top()]>=curr){ // to avoid arr[-1]
s.pop();
}
ans[i]=s.top();
s.push(i); //s now has index
}
return ans;
}
vector<int> prevsmallelement(vector<int> arr, int n){
stack<int> s;
s.push(-1);
vector<int> ans(n);
for(int i=0;i<n;i++){
int curr=arr[i];
while(s.top()!= -1 && arr[s.top()]>=curr){
s.pop();
}
ans[i]=s.top();
s.push(i); //s now has index
}
return ans;
}
int largestRectangle(vector < int > & heights) {
int n=heights.size();
int ansarea=0;
vector<int> nextsmall(n);
vector<int> prevsmall(n);
nextsmall=nextsmallelement(heights,n);
prevsmall =prevsmallelement(heights,n);
for(int i=0;i<n;i++){
if(nextsmall[i]==-1) nextsmall[i]=n;
int w=nextsmall[i]-prevsmall[i] -1;
int area= heights[i] * w;
ansarea=max(area,ansarea);
}
return ansarea;
}