Problem Statement

There are N buildings in a certain one-dimensional landscape. Each building has a height given by hi,i∈[1,N]. If you join K adjacent buildings, they will form a solid rectangle of area K×min(hi,hi+1,…,hi+k−1).

Given N buildings, find the greatest such solid area formed by consecutive buildings.

Input Format 
The first line contains N, the number of buildings altogether. 
The second line contains N space-separated integers, each representing the height of a building.

Constraints 
1≤N≤105 
1≤hi≤106

Output Format 
One integer representing the maximum area of rectangle formed.

Sample Input

5
1 2 3 4 5

Sample Output

9

Explanation 
An illustration of the test case follows.

The problem can be simply seen in this manner. Suppose the height of the ith building is A[i] now we want to find the contiguous segment in the left of i and in the right of i such that all elements are greater or equal to A[i]. To do this we use stack such that whnever we get a house we pop all the elements present in the stack till all the elements are greater as they wont form a continuous element with the ith building

#include<bits/stdc++.h>

#define ff first

using namespace std;

#define lc tree[2*node]

#define rc tree[2*node+1]

#define mid (st+end)/2

#define ss second

#define mp make_pair

#define pb push_back

#define ll long long int 

#define vil vector<ll>

#define vi vector<int>

#define vip vector<pair<int,int> > 

#define vipl vector<pair<ll,ll> > 

#define pp pair<int,int> 

#define ppl pair<ll,ll>

#define ppm pair<ll,int> 

#define mod 1000000007

#define maxn 1000010

#define mn 100010

#define pi 2.0*acos(0.0)

#define vsort(v) sort(v.begin(),v.end())

#define mpp map<int,map<int,int> >

int dx[]={1,-1,0,0,-1,-1,+1,1};

int dy[]={0,0,1,-1,1,-1,-1,1};

int horsex[] = { -2, -2, -1, 1, 2, 2, 1, -1 };

int horsey[] = { 1, -1, -2, -2, -1, 1, 2, 2 };

ll gcd(ll a, ll b)

{

  if(a%b==0) return b;

  else return gcd(b,a%b);

}

ll powmod(ll a ,ll b , ll m)

{

  if(b==0){ return 1;} ll temp=powmod(a,b/2,m); ll val=(temp*temp)%m;

  if(b&1) { return (a*temp)%m;}

  else { return val;}

}

ll power(ll a ,ll b)

{

  if(b==0){ return 1;} ll temp=power(a,b/2); ll val=(temp*temp);

  if(b&1) { return (a*temp);}

  else { return val;}

}

ll invmod(ll a , ll m )

{

return powmod(a,m-2,m);

}

bool ispalin(char str[])

{

 bool f=1;  int l=strlen(str); for(int i=0;i<=(l-1)/2;i++) { if(str[i]!=str[l-i-1])return 0;}

 return 1;

}

ll rev(ll num)

{

  ll ans=0;

  while(num!=0){ int rem=num%10;num=num/10;  ans=ans*10+rem;}

 return ans;

}

int arr[mn];

int main()

{

int n;

scanf("%d",&n);

for(int i=0;i<n;i++)

{

scanf("%d",&arr[i]);

}

ll ans=0;

stack<pp> s;

s.push(mp(arr[0],1));

ans=arr[0];

for(int i=1;i<n;i++)

{

 ll temp=0;

 while(!s.empty() && arr[i]<s.top().ff)

 {

          ll val=s.top().ff;

          ll k=s.top().ss;

          s.pop();

          temp+=k;

          ans=max(ans,temp*val);

        // cout<<"form max "<<temp<<" *"<<" "<<val<<endl;

 

 }

 //cout<<"push "<<arr[i]<<" with temo "<<temp+1<<endl;;

 s.push(mp(arr[i],temp+1));

 

}

//cout<<"exiiiiitttttttttttttt "<<endl;

ll temp=0;

while(!s.empty())

{

    ll val=s.top().ff;

    ll k=s.top().ss;

    temp+=k;

    s.pop();

//    cout<<"form max "<<temp<<" *"<<" "<<val<<endl;

ans=max(ans,temp*val);

    

}

cout<<ans<<endl;

return 0;

}