#include<cstdio>
#include<algorithm>
#include<climits>
#include<cstring>
#define nmax 400003
#define lefts 2*nod
#define rights 2*nod+1
using namespace std;
long long a[nmax],b[nmax],c[nmax],s[nmax],v[nmax],rez,sum;
int n,i,j,k,m,x,y;
void update(int nod,int poz,int st,int dr)
{
    if (st==dr)
    {
        a[nod]=b[nod]=c[nod]=s[nod]=v[poz];
        return;
    }
    int mij=(st+dr)/2;
    if (poz<=mij) update(lefts,poz,st,mij);else
        update(rights,poz,mij+1,dr);
    s[nod]=s[lefts]+s[rights];
    a[nod]=max(a[lefts],s[lefts]+a[rights]);
    b[nod]=max(b[rights],s[rights]+b[lefts]);
    c[nod]=max(max(c[lefts],c[rights]),b[lefts]+a[rights]);
}

void query(int nod,int st,int dr)
{
    if (x<=st && dr<=y)
    {
        rez=max(rez,max(c[nod],sum+a[nod]));
        sum=max(sum+s[nod],b[nod]);
        return;
    }
    int mij=(st+dr)/2;
    if (mij>=x) query(lefts,st,mij);
    if (mij<y) query(rights,mij+1,dr);
}

int main()
{
    freopen("sequencequery.in","r",stdin);
    freopen("sequencequery.out","w",stdout);
    scanf("%d %d",&n,&m);
    fill(a,a+nmax,LONG_MIN);
    fill(b,b+nmax,LONG_MIN);
    fill(c,c+nmax,LONG_MIN);
    for (i=1;i<=n;i++)
        scanf("%lld",&v[i]),update(1,i,1,n);
    for (i=1;i<=m;i++)
    {
        rez=LONG_MIN;
        sum=0;
        scanf("%d %d",&x,&y);
        query(1,1,n);
        printf("%lld\n",rez);
    }
    return 0;
}