#include<stdio.h>
#define Nm (1<<17)
#define m ((l+r)>>1)
#define ls (n<<1)
#define rs (n<<1|1)
#define max(a,b) ((a)>(b)?(a):(b))
int A[Nm];
long long M[Nm<<1],L[Nm<<1],R[Nm<<1],S[Nm<<1];

void build(int n, int l, int r)
{
    if(l==r)
        M[n]=L[n]=R[n]=S[n]=A[l];
    else
    {
        build(ls,l,m);
        build(rs,m+1,r);

        M[n]=max(R[ls]+L[rs],max(M[ls],M[rs]));
        L[n]=max(L[ls],S[ls]+L[rs]);
        R[n]=max(R[rs],S[rs]+R[ls]);
        S[n]=S[ls]+S[rs];
    }
}

int a,b;
long long ans,s;

void query(int n, int l, int r)
{
    if(a<=l && r<=b)
    {
        ans=max(ans,max(M[n],s+L[n]));
        s=max(s+S[n],R[n]);
    }
    else
    {
        if(a<=m)
            query(ls,l,m);
        if(b>m)
            query(rs,m+1,r);
    }
}

int main()
{
    int n,q,i;

    freopen("sequencequery.in","r",stdin);
    freopen("sequencequery.out","w",stdout);

    scanf("%d%d",&n,&q);
    for(i=1;i<=n;++i)
        scanf("%d",A+i);

    build(1,1,n);

    while(q--)
    {
        scanf("%d%d",&a,&b);
        ans=s=-Nm;
        query(1,1,n);
        printf("%lld\n",ans);
    }
    return 0;
}