#include<cstdio>
#include<algorithm>
#include<climits>
#include<cstring>
#define nmax 400003
#define lefts 2*nod
#define rights 2*nod+1
#define MIN -99999999999
using namespace std;
long long A[nmax],B[nmax],C[nmax],Sum[nmax];
long long v[nmax],sol,S;
int m,k,n;
int y,x,i,j;

void Update(int nod,int poz,int st,int dr)
{
    if (st==dr)
    {
        A[nod]=B[nod]=C[nod]=Sum[nod]=v[poz];
        return;
    }
    int mij=(st+dr)/2;
    if (poz<=mij)
        Update(lefts,poz,st,mij);
    else
        Update(rights,poz,mij+1,dr);

    Sum[nod]=Sum[lefts]+Sum[rights];
    A[nod]=max(A[lefts],Sum[lefts]+A[rights]);
    B[nod]=max(B[rights],Sum[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)
    {
        sol=max(sol,max(C[nod],S+A[nod]));
        S=max(S+Sum[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,MIN);fill(B,B+nmax,MIN);fill(C,C+nmax,MIN);

    for (i=1;i<=n;i++)
        {
            scanf("%lld",&v[i]);
            Update(1,i,1,n);
        }

    for (i=1;i<=m;i++)
    {
        sol=MIN;S=0;
        scanf("%d %d",&x,&y);
        Query(1,1,n);
        printf("%lld\n",sol);
    }
}