#include <cstdio>

#define maxn 100001
#define inf -1000000000

FILE *in = fopen("sequencequery.in","r"), *out = fopen("sequencequery.out","w");

int n, m;
int a[maxn];

int A[2<<17];
int B[2<<17];
int C[2<<17];
int Sum[2<<17];

int max(int a, int b)
{
    if ( a > b )
        return a;
    else
        return b;
}

void build(int nod, int st, int dr)
{
    if ( st == dr )
    {
        A[nod] = B[nod] = C[nod] = Sum[nod] = a[st];
        return;
    }

    int q = nod << 1;
    int m = (st + dr) >> 1;

    build(q, st, m);
    build(q+1, m+1, dr);

    A[nod] = max(A[q], Sum[q] + A[q+1]);
    B[nod] = max(B[q] + Sum[q+1], B[q+1]);
    C[nod] = max(max(C[q], C[q+1]), B[q]+A[q+1]);

    Sum[nod] = Sum[q] + Sum[q+1];
}

int p1, p2, S, answ;

void query(int nod, int st, int dr) // a, b
{
    if ( dr < p1 || st > p2 )
        return;

    if ( p1 <= st && dr <= p2 )
    {
        answ = max(answ, max(S + A[nod], C[nod]));
        S = max(S + Sum[nod], B[nod]);

        return;
    }

    if ( st == dr )
        return;

    int q = nod << 1;
    int m = (st + dr) >> 1;

    query(q, st, m);
    query(q+1, m+1, dr);
}

int main()
{
    fscanf(in, "%d %d", &n, &m);

    for ( int i = 1; i <= n; ++i )
        fscanf(in, "%d", &a[i]);

    build(1, 1, n);
    int t, d;
    for ( int i = 1; i <= m; ++i )
    {
        fscanf(in, "%d %d", &t, &d);
        p1 = t;
        p2 = d;

        answ = inf;
        S = inf;
        query(1, 1, n);
        fprintf(out, "%d\n", answ);
    }

	return 0;
}