Untitled

#include<bits/stdc++.h>
using namespace std;
#define int long long 
int kadane(int n,vector<int>&a)
{
    int best=0;
    int sum=0;
    for (int i=0;i<n;++i)
    {
        sum=max(sum+a[i],a[i]);
        best=max(best,sum);
    }
    return best;
}
int sm(int i,int j,int *prf)
{
    if (i==0)return prf[j];
    return prf[j]-prf[i-1];
}
void solve()
{
    int n;
    cin>>n;
    vector<int>a(n+2);
    for (int i=1;i<=n;++i)cin>>a[i];
    vector<int>g(n+2,0);
    int sum=a[1];
    g[1]=a[1];
    for (int i=2;i<=n;++i)
    {
        sum=max(sum+a[i],a[i]);
        g[i]=sum;
    }      
    vector<int>h(n+2);
    h[n]=a[n];
    sum=a[n];
    for (int i=n-1;i>=1;i--)
    {
        sum=max(sum+a[i],sum);
        h[i]=sum;
    }
    int output=a[1],r=1e5;
    for (int i=1;i<=n;i++)
    {
        int sm=0;
        for (int j=i;j>=1;j--)
        {
            sm+=a[j];
            output=max(output,sm*r);
            output=max(output,-sm*r+g[j-1]+h[i+1]);
        }
    }
    cout<<output<<endl;
}
signed main()
{
    int t;
    t=1;
    while(t--)solve();
    return 0;
}