#include<stdio.h>

long long v[400002],a[400002],b[400002],c[400002],sum[400002];
int n,m,st,dr;
long long s,sol;

inline long long max(long long a,long long b)
{return a>b?a:b;}

void init(int l,int r,int x)
{
    if(l==r)
    {
        a[x]=b[x]=c[x]=sum[x]=v[l];
        return;
    }
    int med=(l+r)/2;
    init(l,med,2*x);
    init(med+1,r,2*x+1);

    a[x]=max(a[2*x],sum[2*x]+a[2*x+1]);
    b[x]=max(b[2*x]+sum[2*x+1],b[2*x+1]);
    c[x]=max(max(c[2*x],c[2*x+1]),b[2*x]+a[2*x+1]);
    sum[x]=sum[2*x]+sum[2*x+1];
}


void query(int l,int r,int x)
{
    if(st<=l && dr>=r)
    {
        if(s<0)
            s=0;
        sol=max(sol,max(s+a[x],c[x]));
        s=max(s+sum[x],b[x]);
        return;
    }
    int med=(l+r)/2;
    if(st<=med)
        query(l,med,2*x);
    if(dr>med)
        query(med+1,r,2*x+1);
}


int main()
{
    freopen("sequencequery.in","r",stdin);
    freopen("sequencequery.out","w",stdout);
    int i;
    scanf("%d%d",&n,&m);
    for(i=1;i<=n;++i)
        scanf("%lld",&v[i]);

    init(1,n,1);

    for(i=1;i<=m;++i)
    {
        scanf("%d%d",&st,&dr);
        s=sol=-2000000000;

        query(1,n,1);

        printf("%lld\n",sol);
    }

    return 0;
}