#include <stdio.h>
#include <math.h>
#define lim 100005
int v[lim],s[lim],maxst[lim],maxdr[lim],n,k;
int max(int a,int b){
    if(a>b)
        return a;
    else
        return b;
}
int query(int st,int dr){
    int i,j,sumst=lim*(-1),sumdr=lim*(-1),rasp=lim*(-1),copyst,copydr;
    if(st%k!=1){
        while(st%k!=0){
            if(s[(st/k+1)*k]-s[st-1]>sumst)
                sumst=s[(st/k+1)*k]-s[st-1];
            st++;
        }
        if(s[st]-s[st-1]>sumst)
            sumst=s[st]-s[st-1];
        st++;
    }
    else
        sumst=0;
    if(dr%k!=0){
        while(dr%k!=0){
            if(s[dr]-s[(dr/k)*k]>sumdr)
                sumdr=s[dr]-s[(dr/k)*k];
            dr--;
        }
    }
    else
        sumdr=0;
    rasp=sumst+sumdr;
    if(st>dr)
        return rasp;
    copyst=maxst[st/k];
    copydr=maxdr[dr/k];
    maxst[st/k]=sumst;
    maxdr[dr/k+1]=sumdr;
    for(i=st;i<=n;i+=k)
        for(j=dr;j>=1;j-=k)
            if(maxst[i/k]+maxdr[j/k+1]+s[j]-s[i-1]>rasp)
                rasp=maxst[i/k]+maxdr[j/k+1]+s[j]-s[i-1];
    maxst[st/k]=copyst;
    maxdr[dr/k+1]=copydr;
    return rasp;
}
int main(){
    FILE *fin,*fout;
    fin=fopen("sequencequery.in","r");
    fout=fopen("sequencequery.out","w");
    int i,m,st,dr,sum,rasp;
    fscanf(fin,"%d%d",&n,&m);
    for(i=1;i<=n;i++){
        fscanf(fin,"%d",&v[i]);
        s[i]=s[i-1]+v[i];
    }
    k=sqrt(n);
    sum=0;
    for(i=1;i<=n;i++){
        sum=max(sum+v[i],v[i]);
        if(i%k==0){
            maxst[i/k]=sum;
            sum=0;
        }
    }
    if(sum!=0)
        maxst[n/k+1]=sum;
    sum=0;
    for(i=n;i>=1;i--){
        sum=max(sum+v[i],v[i]);
        if((i-1)%k==0){
            maxdr[i/k+1]=sum;
            sum=0;
        }
    }
    for(i=1;i<=m;i++){
        fscanf(fin,"%d%d",&st,&dr);
        rasp=query(st,dr);
        fprintf(fout,"%d\n",rasp);
    }
    fclose(fin);
    fclose(fout);
    return 0;
}