jungla

#include <iostream>
#define lim 1000005
using namespace std;
int v[lim],ans[lim],stiva[lim],st[lim],dr[lim];

int  main()
{
    int n,cerinta;
    cin>>cerinta;
    if(cerinta==1)
    {   /// aflam brut cate elemente dinaintea lui v[i] sunt mai mici decat v[i]
        int q;
        cin>>n>>q;
        for(int i=1; i<=n; ++i)
        {
            int a;
            cin>>v[i];
            a=0;
            for(int j=i-1; j; --j)
            {
                if(v[j] < v[i]) ++a;
            }
            ans[i]=a;
        }
        for(int i=1; i<=q; ++i)
        {
            int nr;
            cin>>nr;
            cout<<ans[nr]<<'\n';
        }
    }
    else
    {
        int height=0,vf=0;
        /// height reprezinta valoarea maxima din vectorul v,iar vf reprezinta varful stivei
        cin>>n;
        int a;
        for(int i=1; i<=n; ++i)
        {
            cin>>a;
            v[i]=a;
            height=max(height,v[i]);
            while(vf && v[i] > v[stiva[vf]])
            {
                dr[stiva[vf]]=i;
                --vf;
            }
            stiva[++vf]=i;
        }
        for(int i=1; i<=vf; ++i)
            dr[stiva[i]]=n+1;
        vf=0;
        for(int i=n; i; --i)
        {
            while(vf&&v[i]>v[stiva[vf]])
            {
                st[stiva[vf]]=i;
                --vf;
            }
            stiva[++vf]=i;
        }
        long long s,maxs=0;
        for(int i=1; i<=n; ++i)
        {
            int leftlim=st[i]+1,rightlim=dr[i]-1;
            s=(rightlim-leftlim+1)*(height-v[i]);
            maxs=max(s,maxs);
        }
        cout<<maxs;
    }
    return 0;
}