#include <cstdio>

#define maxn 100001

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

int n, m;
int a[maxn];

int arbA[2<<16];
int arbB[2<<16];
int arbC[2<<16];
int arbSum[2<<16];

inline int max(int a, int b)
{
    if ( a > b )
        return a;
    else
        return b;
}
//void build(int n, int l, int r)
//{
//	if (l == r) {
//		A[n] = B[n] = C[n] = max(v[l], 0);
//		Sum[n] = v[l];
//	} else {
//		build(lf, l, md);
//		build(rt, md+1, r);
//
//		A[n] = max(A[lf], Sum[lf]+A[rt]);
//		B[n] = max(B[lf]+Sum[rt], B[rt]);
//		C[n] = max(max(C[lf], C[rt]), B[lf]+A[rt]);
//
//		Sum[n] = Sum[lf]+Sum[rt];
//	}
//}
void build(int nod, int st, int dr)
{
    if ( st == dr )
    {
        arbA[nod] = arbB[nod] = arbC[nod] = max(a[st], 0);
        arbSum[nod] = a[st];
        return;
    }

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

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

    arbA[nod] = max(arbA[q], arbSum[q] + arbA[q+1]);
    arbB[nod] = max(arbB[q] + arbSum[q+1], arbB[q+1]);
    arbC[nod] = max(max(arbC[q], arbC[q+1]), arbA[q] + arbB[q+1]);

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

int p1, p2, r, rr;

void query(int nod, int st, int dr)
{
	if ( p1 <= st && dr <= p2 )
	{
		if ( rr < 0 )
            rr = 0;
		r = max(r, max(rr + arbA[nod], arbC[nod]));
		rr = max(rr + arbSum[nod], arbB[nod]);
	}
	else
	{
	    int m = (st + dr) >> 1;
	    int q = nod << 1;

		if ( p1 <= m )
            query(q, st, m);
		if ( p2 > 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;
        if ( p1 == p2 )
        {
            fprintf(out, "%d\n", a[p1]);
            continue;
        }
        r = rr = 0;
        query(1, 1, n);
        fprintf(out, "%d\n", r);
    }

	return 0;
}