#include <cstdio>
#include <algorithm>
using namespace std;
const int MAX_N = 100001;
const int INF = 0x3f3f3f3f;
struct aint{
int max, tot, st, dr;
} a[MAX_N * 4];
int n, m, s, sol;
int v[MAX_N];
void init(int nod, int st, int dr)
{
if (st == dr)
{
a[nod].max = a[nod].tot = a[nod].st = a[nod].dr = v[st];
return;
}
int mij = (st + dr) / 2;
init(nod * 2, st, mij);
init(nod * 2 + 1, mij + 1, dr);
a[nod].max = max(max(a[nod * 2].max, a[nod * 2 + 1].max), a[nod * 2].dr + a[nod * 2 + 1].st);
a[nod].tot = a[nod * 2].tot + a[nod * 2 + 1].tot;
a[nod].st = max(a[nod * 2].st, a[nod * 2].tot + a[nod * 2 + 1].st);
a[nod].dr = max(a[nod * 2 + 1].dr, a[nod * 2 + 1].tot + a[nod * 2].dr);
}
void query(int nod, int st, int dr, int l, int r)
{
int ret = 0;
if (l <= st && dr <= r)
{
ret = a[nod].max;
if (ret < s + a[nod].st)
ret = s + a[nod].st;
if (s + a[nod].tot > a[nod].dr)
s += a[nod].tot;
else
s= a[nod].dr;
if (sol < ret)
sol = ret;
return;
}
int mij = (st + dr) / 2;
if (l <= mij)
query(nod * 2, st, mij, l, r);
if (mij < r)
query(nod * 2 + 1, mij + 1, dr, l, r);
}
int main()
{
int i;
freopen("sequencequery.in", "r", stdin);
freopen("sequencequery.out", "w", stdout);
scanf("%d %d", &n, &m);
for (i = 1; i <= n; ++i)
scanf("%d", &v[i]);
init(1, 1, n);
for (i = 1; i <= m; ++i)
{
int x, y;
scanf("%d %d", &x, &y);
s = 0;
sol = -INF;
query(1, 1, n, x, y);
printf("%d\n", sol);
}
}