#include <bits/stdc++.h>
using namespace std;
ifstream fin("sequencequery.in");
ofstream fout("sequencequery.out");
#define ll long long
const int Nmax = 100000 + 5;
const ll minl = -2000000000000;
ll n, m, A[4 * Nmax], B[4 * Nmax], C[4 * Nmax], S[4 * Nmax], s, ans, x[Nmax];
void update(int nod, int l, int r)
{
int mid = l + (r - l)/2;
if(l == r)
{
A[nod] = B[nod] = C[nod] = x[l];
S[nod] = x[l];
return;
}
update(2 * nod, l, mid);
update(2 * nod + 1, mid + 1, r);
S[nod] = S[2 * nod] + S[2 * nod + 1];
A[nod] = max(S[2 * nod] + A[2 * nod + 1], A[2 * nod]);
B[nod] = max(S[2 * nod + 1] + B[2 * nod], B[2 * nod + 1]);
C[nod] = max(max(C[2 * nod], C[2 * nod + 1]), A[2 * nod + 1] + B[2 * nod]);
}
void query(int nod, int l, int r, int L, int R)
{
int mid = l + (r - l) / 2;
if(l > R || r < L)return;
if(L <= l && R >= r)
{
ans = max(ans, max(s + A[nod], C[nod]));
s = max(s + S[nod], B[nod]);
return;
}
query(2 * nod, l, mid, L, R);
query(2 * nod + 1, mid + 1, r, L, R);
}
int main()
{
fin >> n >> m;
for(int i = 1; i <= n; ++i)
fin >> x[i];
update(1, 1, n);
for(int i = 1, a, b; i <= m; ++i)
{
fin >> a >> b;
s = 0; ans = minl;
query(1, 1, n, a, b);
fout << ans << '\n';
}
return 0;
}