#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
#define Inf 0x3f3f3f3f
const int Lim = 1e5, Nmax = 1e5+1;
int p = Lim-1;
ll suma,ans=-Inf,n,q;
ll adi[4*Nmax],st[4*Nmax],sum[4*Nmax],dr[4*Nmax];
char s[Lim];
void next()
{
    if(++p == Lim)
        fread(s,1,Lim,stdin), p = 0;
}

void Get(ll &x)
{
    while(s[p]!='-' && !isdigit(s[p]))
        next();
    int semn = 1;
    if(s[p]=='-')
    {
        semn = -1;
        next();
    }
    for(x=0;isdigit(s[p]);next())
        x = x * 10 + s[p] - '0';
    x *= semn;
}

void Build(ll nod,ll l,ll r)
{
    if(l==r)
    {
        ll c;
        Get(c);
        adi[nod] = c;
        st[nod] = dr[nod] = sum[nod] = c;
        return;
    }
    else
    {
        ll mij = (l+r)/2;
        Build(2*nod,l,mij);
        Build(2*nod+1,mij+1,r);
        st[nod] = max(st[2*nod],sum[2*nod]+st[2*nod+1]);
        dr[nod] = max(dr[2*nod+1],dr[2*nod]+sum[2*nod+1]);
        sum[nod] = sum[2*nod] + sum[2*nod+1];
        adi[nod] = max({adi[2*nod],adi[2*nod+1],dr[2*nod]+st[2*nod+1]});
    }
}

void Update(ll nod,ll l,ll r,ll poz,ll val)
{
    if(l==r)
    {
        adi[nod] = max(val,0ll);
        st[nod] = dr[nod] = sum[nod] = val;
        return;
    }
    else
    {
        ll mij = (l+r)/2;
        if(poz<=mij)
            Update(2*nod,l,mij,poz,val);
        else Update(2*nod+1,mij+1,r,poz,val);
        sum[nod] = sum[2*nod]+sum[2*nod+1];
        st[nod] = max(st[2*nod],st[2*nod+1]+sum[2*nod]);
        dr[nod] = max(dr[2*nod+1],dr[2*nod]+sum[2*nod+1]);
        adi[nod] = max({adi[2*nod],adi[2*nod+1],st[2*nod+1]+dr[2*nod]});
    }
}

void Query(ll nod,ll l,ll r,ll a,ll b)
{
    if(a<=l&&r<=b)
    {
        ans = max(ans,max(suma+st[nod],adi[nod]));
        suma = max(suma+sum[nod],dr[nod]);
        //printf("%lld %lld %lld %lld\n",l,r,suma,ans);
        return;
    }
    else
    {
        ll mij = (l+r)/2;
        if(mij>=a)
            Query(2*nod,l,mij,a,b);
        if(mij<b)
            Query(2*nod+1,mij+1,r,a,b);
    }
}

int main()
{
    freopen("sequencequery.in","r",stdin);
    freopen("sequencequery.out","w",stdout);
    Get(n);
    Get(q);
    Build(1,1,n);
    for(int i=1;i<=q;i++)
    {
        suma = 0;
        ans = -Inf;
        ll a,b;
        Get(a);
        Get(b);
        Query(1,1,n,a,b);
        printf("%lld\n",ans);
    }
    return 0;
}