#include <fstream>
using namespace std;
ifstream cin("sequencequery.in");
ofstream cout("sequencequery.out");
const int dim = 100001;
struct nod
{
int pref;
int suf;
int sum;
int secv;
};
int v[dim];
nod A[4 * dim];
nod up_node(nod left, nod right)
{
nod aux;
aux.sum = left.sum + right.sum;
aux.pref = max(left.pref, left.sum + right.pref);
aux.suf = max(right.suf, right.sum + left.suf);
aux.secv = max(right.pref + left.suf, max(left.secv, right.secv));
return aux;
}
void build(int nod, int left, int right)
{
if (right == left)
{
A[nod].sum = v[left];
A[nod].suf = v[left];
A[nod].pref = v[left];
A[nod].secv = v[left];
}
else
{
int mid = (left + right) >> 1;
build(nod * 2, left, mid);
build(nod * 2 + 1, mid + 1, right);
A[nod] = up_node(A[nod * 2], A[nod * 2 + 1]);
}
}
nod query(int node, int left, int right, int a, int b)
{
if (left >= a && right <= b)
return A[node];
else
{
int mid = (left + right) >> 1;
nod l, r;
if (b <= mid)
return query(node * 2, left, mid, a, b);
if (a > mid)
return query(node * 2 + 1, mid + 1, right, a, b);
l = query(node * 2, left, mid, a, b);
r = query(node * 2 + 1, mid + 1, right, a, b);
return up_node(l, r);
}
}
int main()
{
int n, m, x, y, i;
cin >> n >> m;
for (i = 1; i <= n; ++i)
cin >> v[i];
build(1, 1, n);
for (i = 1; i <= m; ++i)
{
cin >> x >> y;
cout << query(1, 1, n, x, y).secv << '\n';
}
return 0;
}