POJ2559 Largest Rectangle in a Histogram

#include<cstdio>
#include<iostream>
#include<cstring>
#include<cmath>
#include<vector>
#include<queue>
#include<map>
#include<set>
#include<algorithm>
using namespace std;
inline void read(long long &a)
{
    long long k=1; a=0; char c=getchar();
    while(c<‘0‘||‘9‘<c){if(c==‘-‘)k=-1; c=getchar();}
    while(‘0‘<=c&&c<=‘9‘){a=a*10+c-‘0‘; c=getchar();}
    a*=k;
}
inline void write(long long a)
{
    if (a<0){putchar(‘-‘);a=-a;}
    if (a>9)write(a/10);
    putchar(a%10+‘0‘);
    return ;
}
long long a[100005],sta[100005],l[100005],r[100005];
int main()
{
    long long n,i,j;
    cin>>n;
    for (i=1;i<=n;i++)
    read(a[i]),l[i]=i,r[i]=i;
    long long top=1;
    a[0]=0;
    for (i=1;i<=n;i++)
    {
        while (a[sta[top]]>=a[i])
        {
            l[i]=l[sta[top]];
            top--;
        }
        sta[++top]=i;
    }
    memset(sta,0,sizeof(sta));
    a[n+1]=0;
    top=1;
    for (i=n;i>=1;i--)
    {
        while (a[sta[top]]>=a[i])
        {
            r[i]=r[sta[top]];
            top--;
        } 
        sta[++top]=i;
    }
    long long ans=0;
    for (i=1;i<=n;i++)
    {
        ans=max(ans,a[i]*(r[i]-l[i]+1));
    }
    cout<<ans<<endl;
    return 0;
}