#include<cstdio>
#include<algorithm>
#define Nmax 100010
using namespace std;

int N,M;
int v[Nmax],A,B,val,poz_e,s[Nmax];

struct asd{
	int st;
	int dr;
	int m;
} a[Nmax];

void update(int nod,int st, int dr){
   if(st==dr){	
	   a[nod].m=val;
	   a[nod].st=val;
	   a[nod].dr=val;
	   return;
   }
   
   int mij=(st+dr)/2;
   
   if(poz_e <= mij)update(2*nod,st,mij);
   else update(2*nod+1,mij+1,dr);
   
   a[nod].m=max(a[2*nod].m,a[2*nod+1].m);
   
   a[nod].st = a[2*nod].st;
   if( s[mij]-s[st-1] + a[2*nod+1].st  > a[nod].st )
	    a[nod].st =s[mij]-s[st] + a[2*nod+1].st ;
   
   a[nod].dr=a[2*nod+1].dr;
   if( s[dr]-s[mij] + a[2*nod].dr > a[nod].dr )
	   a[nod].dr = s[dr]-s[mij] + a[2*nod].dr;
   
   a[nod].m=max(a[nod].m,max(a[nod].st,a[nod].dr));
}

void query(int nod,int st,int dr){
    	
	
	
}
int main(){
	
	freopen("sequencequery.in","r",stdin);
	freopen("sequencequery.out","w",stdout);
	
	scanf("%d%d",&N,&M);
	
	for(int i=1;i<=N;++i){
		scanf("%d",&val);
		poz_e=i;
		v[i]=val;
		s[i]=s[i-1]+val;
		update(1,1,N);
	}
	/*
	for(int i=1;i<=M;++i){
		int A,B;
		scanf("%d%d",&A,&B);
		query(1,N);
	}*/
	
return 0;
}