#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;

int 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;
}