#include <cstdio>
const int NMAX = 1 << 17;
const int MMAX = 1 << 18;
int N, M, a, b;
int V[NMAX];
long long A[MMAX], B[MMAX], C[MMAX], D[MMAX];
long long S, rez;
/*
* A[] suma tuturor elem din st - dr
* B[] suma secventei maxime
* C[] suma maxima din stanga
* D[] suma maxima din dreapta
*/
template <typename T> T max(T a, T b) { return a > b ? a : b; }
void construct(int i, int st, int dr) {
if (st == dr) {
A[i] = B[i] = C[i] = D[i] = V[st];
} else {
int mij, is, id;
mij = (st + dr) >> 1;
is = i << 1; id = is | 1;
construct(is, st, mij);
construct(id, mij + 1, dr);
A[i] = A[is] + A[id];
B[i] = max( max(B[is], B[id]), D[id] + C[is]);
C[i] = max(C[is], A[is] + C[id]);
D[i] = max(D[id], A[id] + D[is]);
}
}
void query(int i, int st, int dr) {
if (a <= st && dr <= b) {
rez >?= max(S + C[i], B[i]);
S = max(S + A[i], D[i]);
} else {
int mij, is;
mij = (st + dr) >> 1;
is = i << 1;
if (a <= mij) query(is, st, mij);
if (mij < b) query(is | 1, mij + 1, dr);
}
}
int main(void) {
FILE *fin = fopen("sequencequery.in", "rt");
FILE *fout = fopen("sequencequery.out", "wt");
int i;
fscanf(fin, " %d %d", &N, &M);
for (i = 1; i <= N; ++i)
fscanf(fin, " %d", V + i);
construct(1, 1, N);
for (i = 0; i < M; ++i) {
fscanf(fin, " %d %d", &a, &b);
rez = V[a]; S = 0; query(1, 1, N);
fprintf(fout, "%lld\n", rez);
}
fclose(fin);
fclose(fout);
return 0;
}