#include<stdio.h>
#include<algorithm>
#include<vector>
#define fs first
#define sc second
#define mp make_pair
#define pb push_back
#define MOD 666013
#define Nmax 101010
using namespace std;
long long best[4*Nmax+100],stx[4*Nmax+100],drx[4*Nmax+100],allx[4*Nmax+100],v[Nmax],maxim,M,x,z,y;
int N;
void update(int nod,int poz,int val,int st,int dr)
{
if(st==dr)
{
best[nod]=val;
stx[nod]=val;
drx[nod]=val;
allx[nod]=val;
}
else
{
int mij=(st+dr)/2;
if(poz<=mij)
update(2*nod,poz,val,st,mij);
else
update(2*nod+1,poz,val,mij+1,dr);
int lt = 2*nod;
int rt = 2*nod+1;
stx[nod] = max(stx[lt],allx[lt]+stx[rt]);
drx[nod] = max(drx[rt],allx[rt]+drx[lt]);
allx[nod] = allx[lt] + allx[rt];
best[nod] = max(best[lt],best[rt]);
best[nod] = max(best[nod],drx[lt] + stx[rt]);
}
return;
}
long long retst,retdr,retall,retbest;
void maxa(int nod,int ist,int idr,int st,int dr)
{
// printf("%d %d %d!\n",st,dr,aint[nod]);
if(ist<=st&&idr>=dr)
{
retst = stx[nod];
retdr = drx[nod];
retall = allx[nod];
retbest = best[nod];
}
else
{
int mij=(st+dr)/2;
long long rs1,rd1,ra1,rb1,rs2,rd2,ra2,rb2,ok=0;
if(ist<=mij){
maxa(2*nod,ist,idr,st,mij);
++ok;
rs1=retst;
rd1=retdr;
ra1=retall;
rb1=retbest;
}
if(idr>mij)
{
maxa(2*nod+1,ist,idr,mij+1,dr);
++ok;
rs2=retst;
rd2=retdr;
ra2=retall;
rb2=retbest;
}
if(ok == 2){
retst = max(rs1,ra1+rs2);
retdr = max(rd2,ra2+rd1);
retall = ra1 + ra2;
retbest = max(rb1,rb2);
retbest = max(retbest,rs2+rd1);
}
}
}
int main(){
freopen("sequencequery.in","r",stdin);
freopen("sequencequery.out","w",stdout);
scanf("%d%d",&N,&M);
for(int i=1;i<=N;++i){
int x;
scanf("%d",&x);
update(1,i,x,1,N);
}
//printf("%d ",best[1]);
for(int i=1;i<=M;++i){
int x,y;
scanf("%d%d",&x,&y);
maxa(1,x,y,1,N);
printf("%d\n",retbest);
}
return 0;
}