#include <cstdio>
#include <algorithm>
#define NMax 400000
#define oo 1LL<<60
#define ll long long
using namespace std;

ll L[NMax+1];
ll R[NMax+1];
ll S[NMax+1];
ll M[NMax+1];
ll sum,res;
int T,N,n;

void Build()
{
    int i;

    for(i = N+n; i <= 2*N-1; ++i) L[i] = R[i] = M[i] = S[i] = -oo;
    for(i = N-1; i >= 1; --i)
    {
        L[i] = max(L[2*i], S[2*i] + L[2*i+1]);
        R[i] = max(R[2*i+1], S[2*i+1] + R[2*i]);
        M[i] = max(M[2*i], max(M[2*i+1], L[2*i+1] + R[2*i]));
        S[i] = S[2*i] + S[2*i+1];
    }
}

void Read()
{
    int i,x;

    scanf("%d %d",&n,&T);
    for(N = 1; N < n; N*=2);
    for(i = 1; i <= n; ++i)
    {
        scanf("%d",&x);
        L[N+i-1] = R[N+i-1] = M[N+i-1] = S[N+i-1] = x;
    }
}

void Query(int p, int x, int y, int st, int dr)
{
    if(x==st && y==dr)
    {
        res = max(res, sum+L[p]);
        res = max(res, sum+S[p]);
        res = max(res, M[p]);
        sum = max(S[p]+sum, R[p]);
        return;
    }

    int mid = (st+dr)/2;
    if( y <= mid ) Query(2*p, x, y, st, mid);
    else if( mid < x ) Query(2*p+1, x, y, mid+1, dr);
    else{ Query(2*p, x, mid, st, mid); Query(2*p+1, mid+1, y, mid+1, dr); }
}

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

    int x,y;

    Read();
    Build();

    while(T--)
    {
        res = -oo; sum = 0;
        scanf("%d %d",&x,&y);
        Query(1,x,y,1,N);
        printf("%lld\n",res);
    }


return 0;
}