#include<cstdio>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std;
const int maxn=500010,inf=0x3f3f3f3f;
int t[maxn][2],f[maxn],num[maxn],L[maxn],R[maxn],M[maxn],sum[maxn],en[maxn],delta[maxn],g[maxn],s[maxn];
//f父亲 num值 L左起最大子段和 R右起最大子段和 M最大子段和 sum和 en覆盖标记 delta覆盖值 g翻转标记 s结点数 
queue<int>q;
int Node(int fa,int number)
{
    int i=q.front();q.pop();
    f[i]=fa;num[i]=sum[i]=L[i]=R[i]=M[i]=number;s[i]=1;
    en[i]=delta[i]=g[i]=t[i][0]=t[i][1]=0;
}
void clear(int x)
{
    q.push(x);
    if(t[x][0])clear(t[x][0]);
    if(t[x][1])clear(t[x][1]);
    t[x][0]=t[x][1]=f[x]=0;
    //
}
void count(int x)//更新记得加自身 
{
    L[x]=max(L[t[x][0]],sum[t[x][0]]+num[x]+L[t[x][1]]);
    R[x]=max(R[t[x][1]],sum[t[x][1]]+num[x]+R[t[x][0]]);
    M[x]=max(M[t[x][0]],M[t[x][1]]);
    M[x]=max(M[x],R[t[x][0]]+L[t[x][1]]+num[x]);
    sum[x]=sum[t[x][0]]+sum[t[x][1]]+num[x];
    s[x]=s[t[x][0]]+s[t[x][1]]+1;
}
void pushdown(int x)
{
    if(g[x])
    {
        g[t[x][0]]^=1;g[t[x][1]]^=1;
        swap(L[t[x][0]],R[t[x][0]]);
        swap(L[t[x][1]],R[t[x][1]]);
        g[x]=0;
    }
    if(en[x])
    {
        en[t[x][0]]=en[t[x][1]]=1;
        delta[t[x][0]]=delta[t[x][1]]=delta[x];
        L[t[x][0]]=R[t[x][0]]=M[t[x][0]]=delta[x]>0?delta[x]*s[t[x][0]]:0;
        sum[t[x][0]]=delta[x]*s[t[x][0]];
        num[t[x][0]]=delta[x];
        L[t[x][1]]=R[t[x][1]]=M[t[x][1]]=delta[x]>0?delta[x]*s[t[x][1]]:0;
        sum[t[x][1]]=delta[x]*s[t[x][1]];
        num[t[x][1]]=delta[x];
        en[x]=0;
    }
}
int rotate(int x)
{
    int y=f[x];
    int k=t[y][1]==x;
    t[y][k]=t[x][!k];f[t[x][!k]]=y;
    t[f[y][t[f[y]][1]==y]=x;f[x]=f[y];f[y]=x;
    t[x][!k]=y;
    L[x]=L[y];R[x]=R[y];M[x]=M[y];sum[x]=sum[y];s[x]=s[y];en[x]=en[y];delta[x]=delta[y];g[x]=g[y];
    count(y);
}
int splay(int x,int y)//因为到达时y已经被旋转走，所以要通过fa[y]来判断 
{
    int fa=f[y];
    while(f[x]!=fa)
    {
        if(f[f[x]]==fa){rotate(x);break;}
        int X=t[f[x]][1]==x,Y=t[f[f[x]]][1]==x;
        if(X^Y)rotate(x),rotate(x);
         else rotate(f[x]),rotate(x);
    }
}
void find(int &r,int x)
{
    for(int i=r;i!=0;)
    {
        pushdown(i);
        if(x<=s[t[i][0]])i=t[i][0];else
        if(x==s[t[i]][0]+1){splay(i,r);r=i;break;}
        else{x-=s[t[i][0]]+1;i=t[i][1];}
    }    
}
void build(int fa,int &x,int l,int r)
{
    if(l>r)return;
    int mid=(l+r)>>1;
    x=Node(fa,a[mid]);
    if(l<mid)build(x,t[x][0],l,mid-1);
    if(r>mid)build(x,t[x][1],mid+1,r);
    count(x);
}
void insert()
{
    int l,k;
    scanf("%d%d",&l,&k);
    for(int i=1;i<=k;i++)scanf("%d",&a[i]);
    int r;build(0,r,1,k);
    find(root,l);find(t[root][1],0);//?
    t[t[root][1]][0]=r;
    count(t[root][1]);count(root);
}
void del()
{
    int l,k;
    scanf("%d%d",&l,&k);
    find(root,l-1);find(t[root][1],k);
    clear(t[t[root][1]][0]);t[t[root][1]][0]=0;
}
void cover()
{
    int l,k,number;
    scanf("%d%d%d",&l,&k,&number);
    find(root,l-1);find(t[root][1],k);
    int y=t[t[root][1]][0];
    en[y]=1;
    delta[y]=number;
    L[y]=R[y]=M[y]=delta[y]>0?delta[y]*s[y]:0;
    sum[y]=delta[y]*s[y];
    num[y]=delta[y];
}
void reverse()
{
    int l,k;
    scanf("%d%d%d",&l,&k);
    find(root,l-1);find(t[root][1],k);
    int y=t[t[root][1]][0];
    g[y]^=1;
    swap(L[y],R[y]);
}
int getsum()
{
    int l,k;
    scanf("%d%d%d",&l,&k);
    find(root,l-1);find(t[root][1],k);
    int y=t[t[root][1]][0];
    return sum[y];
}
int getM()
{
    int l,k;
    scanf("%d%d%d",&l,&k);
    find(root,l-1);find(t[root][1],k);
    int y=t[t[root][1]][0];
    return M[y];
}
char str[20];
int main()
{
    scanf("%d%d",&n,&m);
    //0?
    for(int i=maxn;i>=1;i--)q.push(i);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    int root=0;
    build(0,root,1,n);