#include<stdio.h>
#include<string.h>
#define inf -100001
 
long long int A[500000],B[500000],C[500000],Sum[500000],val,poz,start,stop,S,maxim;
 
inline long long int max(long long int a,long long int b)
{
    if(a>b)
        return a;
    return b;
}
 
void update(int nod,int st,int dr)
{
    int div;
 
    if(st==dr)
    {
        A[nod]=B[nod]=C[nod]=Sum[nod]=val;
        return;
    }
 
    div=(st+dr)/2;
    if(poz<=div)
        update(2*nod+1,st,div);
    else
        update(2*nod+2,div+1,dr);
    A[nod]=max(A[2*nod+1],Sum[2*nod+1]+A[2*nod+2]);//subsecventa de suma maxima la inceputul intervalului
    B[nod]=max(B[2*nod+2],Sum[2*nod+2]+B[2*nod+1]);//subsecventa de suma maxima la sfarsitul intervalului
    C[nod]=max(B[2*nod+1]+A[2*nod+2],max(C[2*nod+1],C[2*nod+2]));//subsecventa de suma maxima din interval
    Sum[nod]=Sum[2*nod+1]+Sum[2*nod+2];//suma numerelor din interval
}
 
void query(int nod,int st,int dr)
{
    int div;
 
    if(start<=st && dr<=stop)
    {
        maxim=max(maxim,max(C[nod],A[nod]+S));
        S=max(S+Sum[nod],B[nod]);
    }
    else
    {
        div=(st+dr)/2;
        if(start<=div)
            query(2*nod+1,st,div);
        if(stop>div)
            query(2*nod+2,div+1,dr);
    }
}

int main()
{
    int n,x,y,i,m;
    FILE *f=fopen("sequencequery.in","r");
    FILE *g=fopen("sequencequery.out","w");
 
    memset(A,0,sizeof(A));
    memset(B,0,sizeof(B));
    memset(C,0,sizeof(C));
    memset(Sum,0,sizeof(Sum));
 
    fscanf(f,"%i%i",&n,&m);
    for(i=0;i<n;i++)
    {
        fscanf(f,"%lli",&val);
        poz=i;
        update(0,0,n-1);
    }
 
    for(i=0;i<m;i++)
    {
        fscanf(f,"%i%i",&x,&y);
        x--;
        y--;
        start=x;
        stop=y;
        maxim=inf;
        S=0;
        query(0,0,n-1);
        fprintf(g,"%lli\n",maxim);
    }
    fclose(f);
    fclose(g);
    return 0;
}