#include<stdio.h>

#define ll long long
#define INF ((ll)1<<61)
#define LARB 270005
#define maxim(a,b) (a>b ? a : b)

int A[LARB],B[LARB],C[LARB],S[LARB];
int p[105],s[105],n,m,v[100005],nrs;

void query(int n,int st,int dr,int a,int b)
{
    if(a<=st && dr<=b)
    {
        p[++nrs]=n;
        return ;
    }
    int mij=(st+dr)/2;
    if(a<=mij)
        query(2*n,st,mij,a,b);
    if(b>mij)
        query(2*n+1,mij+1,dr,a,b);
}

void update(int n,int st,int dr)
{
    if(st==dr)
    {
        A[n]=v[st];
        B[n]=C[n]=maxim(v[st],0);
        S[n]=v[st];
        return ;
    }
    int mij=(st+dr)/2;
    update(2*n,st,mij);
    update(2*n+1,mij+1,dr);
    A[n]=maxim(A[2*n],A[2*n+1]);
    A[n]=maxim(A[n],B[2*n]+C[2*n+1]);

    B[n]=maxim(B[2*n+1],S[2*n+1]+B[2*n]);
    C[n]=maxim(C[2*n],S[2*n]+C[2*n+1]);
    S[n]=S[2*n]+S[2*n+1];
}

int main()
{
    int i,j,a,b;
    ll sol,vmax;
    freopen("sequencequery.in","r",stdin);
    freopen("sequencequery.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(i=1;i<=n;i++)
        scanf("%d",&v[i]);
    update(1,1,n);
    for(i=1;i<=m;i++)
    {
        scanf("%d%d",&a,&b);
        nrs=0;
        query(1,1,n,a,b);
        for(j=1;j<=nrs;j++)
            s[j]=s[j-1]+S[p[j]];
        vmax=-INF;sol=-INF;
        for(j=1;j<=nrs;j++)
        {
            sol=maxim(sol,C[p[j]]+s[j-1]+vmax);
            sol=maxim(sol,A[p[j]]);
            vmax=maxim(vmax,B[p[j]]-s[j]);
        }
        printf("%lld\n",sol);
    }
    return 0;
}