Max answer

Alice has a magic array. She suggests that the value of a interval is equal to the sum of the values in the interval, multiplied by the smallest value in the interval.

Now she is planning to find the max value of the intervals in her array. Can you help her?

Input

First line contains an integer n(1 \le n \le 5 \times 10 ^5n(1≤n≤5×105).

Second line contains nn integers represent the array a (-10^5 \le a_i \le 10^5)a(−105≤ai​≤105).

Output

One line contains an integer represent the answer of the array.

 //I-线段树+单调栈

 #include<bits/stdc++.h>

 using namespace std;

 typedef long long ll;

 const int maxn=5e5+;

 const int inf=0x3f3f3f3f;

 #define lson l,m,rt<<1

 #define rson m+1,r,rt<<1|1

 int a[maxn],l[maxn],r[maxn];

 ll pre[maxn],beh[maxn],maxl[maxn<<],minl[maxn<<],maxr[maxn<<],minr[maxn<<];

 void pushup(int rt)

 {

     maxl[rt]=max(maxl[rt<<],maxl[rt<<|]);

     minl[rt]=min(minl[rt<<],minl[rt<<|]);

     maxr[rt]=max(maxr[rt<<],maxr[rt<<|]);

     minr[rt]=min(minr[rt<<],minr[rt<<|]);

 }

 void build(int l,int r,int rt)

 {

     if(l==r){

         maxl[rt]=minl[rt]=beh[l];

         maxr[rt]=minr[rt]=pre[l];

         return ;

     }

     int m=(l+r)>>;

     build(lson);

     build(rson);

     pushup(rt);

 }

 ll query(int op,int L,int R,int l,int r,int rt)

 {

     if(L<=l&&r<=R){

         if     (op==) return maxl[rt];

         else if(op==) return minl[rt];

         else if(op==) return maxr[rt];

         else if(op==) return minr[rt];

     }

     int m=(l+r)>>;

     ll ret;

     if(op==||op==){

         ret=-inf;

         if(L<=m) ret=max(ret,query(op,L,R,lson));

         if(R> m) ret=max(ret,query(op,L,R,rson));

     }

     else if(op==||op==){

         ret=inf;

         if(L<=m) ret=min(ret,query(op,L,R,lson));

         if(R> m) ret=min(ret,query(op,L,R,rson));

     }

     return ret;

 }

 deque<int> deq;//因为是双端队列，所以插的时候要插到头上才能实现栈的功能

 int main()

 {

     int n;

     scanf("%d",&n);

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

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

     }

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

         pre[i]=pre[i-]+a[i];

     }

     for(int i=n;i>=;i--){

         beh[i]=beh[i+]+a[i];

     }

     build(,n,);

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

         while(deq.size()&&a[deq.front()]>=a[i]) deq.pop_front();

         if(deq.empty()) l[i]=;

         else l[i]=deq.front()+;

         deq.push_front(i);

     }

     deq.clear();

     for(int i=n;i>=;i--){

         while(deq.size()&&a[deq.front()]>=a[i]) deq.pop_front();

         if(deq.empty()) r[i]=n;

         else r[i]=deq.front()-;

         deq.push_front(i);

     }

     ll maxx=-inf,ret;

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

         if(a[i]>=){

             ret=query(,l[i],i,,n,);

             ret+=query(,i,r[i],,n,);

             ret=ret-beh[i]-pre[i]+a[i];

             ret*=a[i];

 //            cout<<query(1,l[i],i,1,n,1)<<" "<<query(3,i,r[i],1,n,1)<<endl;

         }

         else{

             ret=query(,l[i],i,,n,);

             ret+=query(,i,r[i],,n,);

             ret=ret-beh[i]-pre[i]+a[i];

             ret*=a[i];

         }

         maxx=max(maxx,ret);

     }

     printf("%lld\n",maxx);

 }