#include<stdio.h>
#define MAX (1<<19)
int N, M, v[MAX];
long long int A[MAX], B[MAX], C[MAX], D[MAX];
long long int S, rez;
long long int max(long long int x, long long int y) { return x > y ? x : y;}
void build(int nod, int left, int right)
{
int middle, l, r;
if (left == right)
{
A[nod] = B[nod] = C[nod] = D[nod] = v[left];
}
else
{
middle = (left + right) / 2;
l = 2 * nod; r = l + 1;
build(l, left, middle);
build(r, middle + 1, right);
A[nod] = max(A[l], D[l] + A[r]);
B[nod] = max(D[r] + B[l], B[r]);
C[nod] = max(max(C[l],C[r]), A[r] + B[l]);
D[nod] = D[l] + D[r];
}
}
void query(int nod, int left, int right, int st, int dr)
{
int l, r, middle;
if (st <= left && right <= dr)
{
if (S < 0) S = 0;
rez = max(rez, max(S + A[nod], C[nod]));
S = max(S + D[nod], B[nod]);
}
else
{
l = nod * 2; r = l + 1;
middle = (left + right) / 2;
if (st <= middle) query(l, left, middle, st, dr);
if (dr > middle) query(r, middle + 1, right, st, dr);
}
}
int main()
{
freopen("sequencequery.in","r",stdin);
freopen("sequencequery.out","w",stdout);
int i, x, y;
scanf("%d %d", &N, &M);
for (i = 1; i <= N; i++) scanf("%d",&v[i]);
build(1,1,N);
for (i = 1; i <= M; i++)
{
scanf("%d %d",&x, &y);
// x++; y++;
S = 0; rez = v[x];
query(1, 1, N, x, y);
// if (rez < 0) rez = 0;
printf("%d\n",rez);
}
return 0;
}