#include <iostream>
using namespace std;
#define N_MAX 100001
#define INF -999999999
int N, M, V[N_MAX];
struct ArbInt {
int st, dr, max, S;
} Arb[4*N_MAX];
int start, finish, maxim, S;
void Build(int nod, int left, int right) {
if(left==right) {
Arb[nod].st=Arb[nod].dr=V[left];
Arb[nod].max=Arb[nod].S=V[left];
return;
}
int mij=(left+right)/2;
Build(2*nod, left, mij);
Build(2*nod+1, mij+1, right);
Arb[nod].max=max(max(Arb[2*nod].max, Arb[2*nod+1].max), Arb[2*nod].dr + Arb[2*nod+1].st);
Arb[nod].S=Arb[2*nod].S + Arb[2*nod+1].S;
Arb[nod].st=max(Arb[2*nod].st, Arb[2*nod].S + Arb[2*nod+1].st);
Arb[nod].dr=max(Arb[2*nod+1].dr, Arb[2*nod+1].S + Arb[2*nod].dr);
}
void Query(int nod, int left, int right) {
if(start<=left && right<=finish) {
int p=Arb[nod].max;
maxim=max(maxim, max(Arb[nod].st+S, p));
S=max(S+Arb[nod].S, Arb[nod].dr);
return;
}
int mij=(left+right)/2;
if(start<=mij) { Query(2*nod, left, mij); }
if(mij<finish) { Query(2*nod+1, mij+1, right); }
}
int main() {
FILE *f1=fopen("sequencequery.in", "r"), *f2=fopen("sequencequery.out", "w");
int i, j, p, q;
fscanf(f1, "%d%d", &N, &M);
for(i=1; i<=N; i++) { fscanf(f1, "%d", &V[i]); }
Build(1, 1, N);
for(i=1; i<=M; i++) {
fscanf(f1, "%d%d", &start, &finish);
S=0; maxim=INF;
Query(1, 1, N);
fprintf(f2, "%d\n", maxim);
}
fclose(f1); fclose(f2);
return 0;
}