#include <fstream>
#include <vector>
#include <algorithm>
#define inf 9000000000000000000
using namespace std;
ifstream in("sequencequery.in");
ofstream out("sequencequery.out");
const int Nmax = 100005;
struct arbore
{
long long st;
long long dr;
long long mij;
long long total;
};
vector<arbore> Arb(4 * Nmax);
long long stanga_trecut, stanga_curent;
long long dreapta_trecut, dreapta_curent;
long long total_trecut, total_curent;
void Update (int poz, int val, int nod, int st, int dr)
{
if (st == dr)
{
Arb[nod].st = 1LL * val;
Arb[nod].dr = 1LL * val;
Arb[nod].mij = 1LL * val;
Arb[nod].total = 1LL * val;
return;
}
int mij = (st + dr) / 2;
if (mij >= poz)
Update(poz, val, nod * 2, st, mij);
else
Update(poz, val, nod * 2 + 1, mij + 1, dr);
Arb[nod].st = max(Arb[nod * 2].st, Arb[nod * 2].total + Arb[nod * 2 + 1].st);
Arb[nod].dr = max(Arb[nod * 2].dr + Arb[nod * 2 + 1].total, Arb[nod * 2 + 1].dr);
Arb[nod].mij = max(max(Arb[nod * 2].mij, Arb[nod * 2 + 1].mij), Arb[nod * 2].dr + Arb[nod * 2 + 1].st);
Arb[nod].total = Arb[nod * 2].total + Arb[nod * 2 + 1].total;
}
void Query (long long&maxim, int Start, int Finish, int nod, int st, int dr)
{
if (st >= Start && dr <= Finish)
{
stanga_curent = max(Arb[nod].st, dreapta_trecut + Arb[nod].st);
dreapta_curent = max(dreapta_trecut + Arb[nod].total, Arb[nod].dr);
total_curent = total_trecut + Arb[nod].total;
maxim = max(maxim, Arb[nod].mij);
maxim = max(maxim, stanga_curent);
maxim = max(maxim, dreapta_curent);
maxim = max(maxim, total_curent);
stanga_trecut = stanga_curent;
dreapta_trecut = dreapta_curent;
total_trecut = total_curent;
return;
}
int mij = (st + dr) / 2;
if (mij >= Start) Query(maxim, Start, Finish, nod * 2, st, mij);
if (mij < Finish) Query(maxim, Start, Finish, nod * 2 + 1, mij + 1, dr);
}
int main()
{
int n, m;
in.sync_with_stdio(false);
in >> n >> m;
if (1LL * n * n * m <= 10000000)
{
vector<int> v(n + 1);
vector<long long> s(n + 1);
for (int i = 1; i <= n; i++)
in >> v[i], s[i] = s[i - 1] + 1LL * v[i];
while (m--)
{
int a, b;
in >> a >> b;
long long maxim = -inf;
for (int i = a - 1; i <= b - 1; i++)
for (int j = i + 1; j <= b; j++)
maxim = max(maxim, s[j] - s[i]);
out << maxim << '\n';
}
return 0;
}
for (int i = 1; i <= n; i++)
{
int x;
in >> x;
Update(i, x, 1, 1, n);
}
for (int i = 1; i <= m; i++)
{
int x, y;
long long maxim = -inf;
in >> x >> y;
Query(maxim, x, y, 1, 1, n);
out << maxim << '\n';
stanga_curent = stanga_trecut = dreapta_curent = dreapta_trecut = total_curent = total_trecut = 0;
}
return 0;
}