#include <cstdio>

#define MAX_N (1 << 17)

#define le (nod << 1)
#define rt (le + 1)
#define md ((li + lf) >> 1)

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

long A[MAX_N], B[MAX_N], C[MAX_N], Sum[MAX_N], V[MAX_N];
int N, M, st, dr;
long S, Sol;

void build(int nod, int li, int lf)
{
    if(li == lf)
    {
        A[nod] = B[nod] = C[nod] = Sum[nod] = V[li];
        return;
    }

    build(le, li, md);
    build(rt, md + 1, lf);

    A[nod] = max(A[le], Sum[le] + A[rt]);
    B[nod] = max(B[rt], Sum[rt] + B[le]);
    C[nod] = max(max(C[rt], C[le]), A[rt] + B[le]);

    Sum[nod] = Sum[rt] + Sum[le];
}

void query(int nod, int li, int lf)
{
    if(li >= st && dr >= lf)
    {
        if(S < 0) S = 0;

        Sol = max(Sol, max(S + A[nod], C[nod]));
        S = max(S + Sum[nod], B[nod]);
        return;
    }

    if(st <= md) query(le, li, md);
    if(dr > md) query(rt, md+1, lf);
}

void citire()
{
    scanf("%d %d",&N, &M);

    for(int i = 1; i <= N; ++i)
        scanf("%ld",V+i);

    build(1, 1, N);
}

void solve()
{
    for(int i = 1; i <= M; ++i)
    {
        scanf("%d %d\n",&st, &dr);

        Sol = V[st], S = 0;
        query(1, 1, N);

        printf("%ld\n",Sol);
    }
}

int main()
{
    freopen("sequencequery.in","rt",stdin);
    freopen("sequencequery.out","wt",stdout);

    citire();
    solve();
}