#include <fstream>
using namespace std;
const int N = 1 << 18;
struct node
{
long long total, pref, suf, smax;
};
bool vis[N];
node t[N];
ifstream in("sequencequery.in");
ofstream out("sequencequery.out");
long long max(long long a, long long b, long long c)
{
return max(a, max(b, c));
}
node combine(node x, node y)
{
node ans;
ans.total = x.total + y.total;
ans.pref = max(x.pref, x.total + y.pref);
ans.suf = max(y.suf, x.suf + y.total);
ans.smax = max(x.smax, y.smax, x.suf + y.pref);
return ans;
}
node q(int p, int l, int r, int a, int b)
{
if (a <= l && r <= b) return t[p];
int m = (l + r) / 2, nl = 2*p, nr = 2*p + 1;
if (a <= m && b > m)
{
node q_l = q(nl, l, m, a, b);
node q_r = q(nr, m+1, r, a, b);
return combine(q_l, q_r);
}
if (a <= m) return q(nl, l, m, a, b);
return q(nr, m+1, r, a, b);
}
void update(int p, int l, int r, int pos, int val)
{
if (l == r)
{
t[p].pref = t[p].smax = t[p].suf = t[p].total = val;
vis[p] = true;
return;
}
int m = (l + r) / 2, nl = 2*p, nr = 2*p + 1;
if (pos <= m) update(nl, l, m, pos, val);
else update(nr, m + 1, r, pos, val);
if (vis[nl] && vis[nr]) t[p] = combine(t[nl], t[nr]);
else if (vis[nl]) t[p] = t[nl];
else t[p] = t[nr];
vis[p] = true;
}
int main()
{
int n, m;
cin >> n >> m;
for (int i = 1; i <= n; i++)
{
int aux;
cin >> aux;
update(1, 1, n, i, aux);
}
for (int i = 0; i < m; i++)
{
int a, b;
in >> a >> b;
node ans = q(1, 1, n, a, b);
cout << ans.smax << "\n";
}
return 0;
}