#include //#include using namespace std; //using namespace atcoder; #define all(v) v.begin(),v.end() using ll = long long; using ull = unsigned long long; using lll = __int128; using vll=vector; using vvll = vector>; using P = pair; using vp=vector>; //using mint=modint1000000007; //using mint=modint998244353; const ll INF=1ll<<60; ll mod10=1e9+7; ll mod99=998244353; const double PI = acos(-1); #define rep(i,n) for (ll i=0;i=0;--i) #define rep2(i,a,n) for (ll i=a;i=n;--i) templatebool chmax(T &a, const T &b) { if (abool chmin(T &a, const T &b) { if (b struct segtree{ using T = typename monoid::Type; ll N; vector node; segtree(ll n){ N=1; while(N(N*2-1,monoid::id()); } T operator [](int k){ return node[N-1+k]; } void update(int k,T x){ k+=N-1; node[k]=x; while(k){ k=(k-1)/2; node[k]=monoid::op(node[2*k+1],node[2*k+2]); } } T query(int a,int b,int k,int l,int r){ if(r<=a||b<=l) return monoid::id(); else if(a<=l&&r<=b) return node[k]; else{ int m=(l+r)/2; return monoid::op(query(a,b,2*k+1,l,m),query(a,b,2*k+2,m,r)); } } T sub(int a,int b){ return query(a,b,0,0,N); } int max_right_sub(ll a,ll b,auto f2){return max_right(a,b,0,0,N,f2,monoid::id()).second;} pair max_right(ll a,ll b,ll k,ll l,ll r,auto f2,T v){ if(r<=a||b<=l){ return {monoid::id(),-1}; }else if(a<=l&&r<=b&&(!f2(monoid::op(node[k],v)))){ return {node[k],-1}; }else if(k>=N-1){ return (f2(monoid::op(v,node[k]))?make_pair(node[k],k-(N-1)):make_pair(node[k],-1ll)); }else{ auto[vr,ir] = max_right(a,b,2*k+2,(l+r)/2,r,f2,v); if(ir!=-1){ return {vr,ir}; }else{ auto [vl,il]= max_right(a,b,2*k+1,l,(l+r)/2,f2,monoid::op(v,vr)); return {vl,il}; } } } int min_left_sub(ll a,ll b,auto f2){return min_left(a,b,0,0,N,f2,monoid::id()).second;} pair min_left(ll a,ll b,ll k,ll l,ll r,auto f2,T v){ if(r<=a||b<=l){ return {monoid::id(),N+1}; }else if(a<=l&&r<=b&&(!f2(monoid::op(node[k],v)))){ return {node[k],N+1}; }else if(k>=N-1){ return (f2(monoid::op(v,node[k]))?make_pair(node[k],k-(N-1)):make_pair(node[k],N+1)); }else{ auto [vl,il] = min_left(a,b,2*k+1,l,(l+r)/2,f2,v); if(il!=N+1){ return {vl,il}; }else{ auto [vr,ir]=min_left(a,b,2*k+2,(l+r)/2,r,f2,monoid::op(v,vl)); return {vr,ir}; } } } }; struct monoid{ using Type = long long; static Type op(Type a,Type b){ return max(a,b); } static Type id(){return -INF;} }; struct monoid2{ using Type = long long; static Type op(Type a,Type b){ return min(a,b); } static Type id(){return INF;} }; bool solve(){ ll N;cin>>N; vll A(N);rep(i,N) cin>>A[i]; vll rw(N+1);rep(i,N) rw[i+1]=rw[i]+A[i]; ll ans=-INF; segtree segl(N+1),segr(N+1); ll mi=0; rep2(r,1,N+1){ segr.update(r,rw[r]-mi); chmin(mi,rw[r]); } ll ma=rw[N]; for(int i=N-1;i>=0;i--){ segl.update(i,ma-rw[i]); chmax(ma,rw[i]); } rep2(i,1,N){ chmax(ans,segr.sub(1,i+1)*segl.sub(i,N)); } segtree segl2(N+1),segr2(N+1); mi=0; rep2(r,1,N+1){ segr2.update(r,rw[r]-mi); chmax(mi,rw[r]); } ma=rw[N]; for(int i=N-1;i>=0;i--){ segl2.update(i,ma-rw[i]); chmin(ma,rw[i]); } rep2(i,1,N){ chmax(ans,segr2.sub(1,i+1)*segl2.sub(i,N)); } cout << ans << endl; return 0; } int main(){ cin.tie(0); ios::sync_with_stdio(false); ll T=1;//cin>>T; rep(i,T) solve(); }