Maximum ractangular area in a histogram

/*
Logic:
M-1: T.C : O(n) S.C : O(n) : 3 pass
Basically we will find the left first min and right first min using stack and then again traversing the array
and distance between left min to right min multiplied by current element height and update the maximum everytime.

M-2: T.C : O(n) S.C : O(n) : 1 pass
Suppose we are finding the last min using stack of pair where stack first element will be index of current element
and second element will be the index of left minimum element(-1 if there is no such element exists)
Steps:
push first element index with -1 because no element before it and start iterating from first index
Case 1: suppose current top element of stack is smaller than current ith element means for ith element,left minimum is top
element index so push current element in stack as {i,st.top().first}.So if any element is in stack that means it's left
minimum index will also be there as second element.

Case 2: Suppose current top element of stack is greater or equal to current element then first right minimum of top
element will be the current element and stack top element second element denotes the left minimum element index so
now we can calculate the area of histogram of arr[i] height by (right-left-1)*top_element_height so find it and update
every time.

After doing for whole array,find all histogram area which is present in stack as their next minimum is not present in array
so consider n as next right min element and update the answer also.
*/


//M-1
#include <bits/stdc++.h>
using namespace std;
class Solution
{
    public:
    long long getMaxArea(long long arr[], int n)
    {
        vector <pair<long long int,long long int>> left_min,right_min;
        stack<pair<long long int,long long int>> st;
        for(int i=0;i<n;i++){
            if(st.empty()){
                left_min.push_back(make_pair(-1,arr[i]));
                st.push(make_pair(i,arr[i]));

            }
            else{
                while(!st.empty() && st.top().second>=arr[i])
                   st.pop();
                if(!st.empty())
                    left_min.push_back(st.top());
                else
                   left_min.push_back(make_pair(-1,arr[i]));
                st.push(make_pair(i,arr[i]));
                }
            }
        while(!st.empty())
           st.pop();
         for(int i=n-1;i>=0;i--){
            if(st.empty()){
                right_min.push_back(make_pair(n,arr[i]));
                st.push(make_pair(i,arr[i]));

            }
            else{
                while(!st.empty() && st.top().second>=arr[i])
                   st.pop();
                if(!st.empty())
                    right_min.push_back(st.top());
                else
                   right_min.push_back(make_pair(n,arr[i]));
                st.push(make_pair(i,arr[i]));
                }
            }
            reverse(right_min.begin(),right_min.end());
            long long int area=INT_MIN;
            for(int i=0;i<n;i++){
                if(area<(arr[i]+abs(left_min[i].first+1-i)*arr[i]+abs(right_min[i].first-i-1)*arr[i]))
                area=(arr[i]+abs(left_min[i].first+1-i)*arr[i]+abs(right_min[i].first-i-1)*arr[i]);
            }
           return area;
    }
};

int main()
 {
    long long t;

    cin>>t;
    while(t--)
    {
        int n;
        cin>>n;

        long long arr[n];
        for(int i=0;i<n;i++)
            cin>>arr[i];
        Solution ob;
        cout<<ob.getMaxArea(arr, n)<<endl;

    }
    return 0;
}

//M-2
class Solution {
long long int _max(long long int a,long long int b){
    if(a>b) return a;
    return b;
}
class Solution
{
    public:
    //Function to find largest rectangular area possible in a given histogram.
    long long getMaxArea(long long arr[], int n)
    {
        stack<pair<int,int>> st;
        long long int ans=arr[0];
        st.push({0,-1});
        for(int i=1;i<n;i++){
            if(arr[i]>=arr[st.top().first]) st.push(make_pair(i,st.top().first));
            else{
                while(st.size() && arr[i]<arr[st.top().first]){
                    pair<int,int> temp=st.top();
                    st.pop();
                    ans=_max(ans,(i-temp.second-1)*arr[temp.first]);
                    }
                if(st.size())st.push(make_pair(i,st.top().first));
                else st.push(make_pair(i,-1));
            }
        }
        while(st.size()){
            ans=_max(ans,(n-st.top().second-1)*arr[st.top().first]);
            st.pop();
        }
        return ans;
    }
};