#include<stdio.h>

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

ll A[LARB],B[LARB],C[LARB],S[LARB];
ll D[LARB],B2[LARB],C2[LARB],P[LARB];
int n,m,v[100005];
ll inf;

void query(int n,int st,int dr,int a,int b)
{
    if(a<=st && dr<=b)
    {
        D[n]=A[n];
        B2[n]=B[n];
        C2[n]=C[n];
        P[n]=S[n];
        return ;
    }
    int mij=(st+dr)/2;
    
    D[2*n]=D[2*n+1]=-inf;
    B2[2*n]=B2[2*n+1]=-inf;
    C2[2*n]=C2[2*n+1]=-inf;
    P[2*n]=P[2*n+1]=-inf;
    
    if(a<=mij)
        query(2*n,st,mij,a,b);
    if(b>mij)
        query(2*n+1,mij+1,dr,a,b);
        
    D[n]=maxim(D[2*n],D[2*n+1]);
    if(D[n]>=0)
        D[n]=maxim(D[n],B2[2*n]+C2[2*n+1]);

    B2[n]=maxim(B2[2*n+1],P[2*n+1]+B2[2*n]);
    C2[n]=maxim(C2[2*n],P[2*n]+C2[2*n+1]);
    P[n]=P[2*n]+P[2*n+1];
}

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]);
    if(A[n]>=0)
        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,a,b;
    
    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);
    inf=200000;
    inf*=inf;
    for(i=1;i<=m;i++)
    {
        scanf("%d%d",&a,&b);
        query(1,1,n,a,b);
        printf("%lld\n",D[1]);
    }
    return 0;
}