#include <bits/stdc++.h>
using namespace std;
const int NMAX = 1e5 + 1;
#define int long long int
struct nod {
int sum;
int pref_sum;
int suff_sum;
int scmax;
};
nod tree[4*NMAX];
int n, m, v[NMAX];
nod mergee(nod stanga, nod dreapta) {
nod ans;
ans.sum = stanga.sum + dreapta.sum;
ans.pref_sum = max(stanga.pref_sum, stanga.sum + dreapta.pref_sum);
ans.suff_sum = max(dreapta.suff_sum, dreapta.sum + stanga.suff_sum);
ans.scmax = max({stanga.scmax, dreapta.scmax, stanga.suff_sum + dreapta.pref_sum});
return ans;
}
void build(int node, int st, int dr) {
if (st == dr)
tree[node].sum = tree[node].pref_sum = tree[node].scmax = tree[node].suff_sum = v[st];
else {
int mij = (st + dr) / 2;
build(node*2, st, mij);
build(node*2+1, mij+1, dr);
tree[node].sum = tree[node*2].sum + tree[node*2+1].sum;
tree[node].pref_sum = max(tree[node*2].pref_sum, tree[node*2].sum + tree[node*2+1].pref_sum);
tree[node].suff_sum = max(tree[node*2+1].suff_sum, tree[node*2+1].sum + tree[node*2].suff_sum);
tree[node].scmax = max({tree[node*2].scmax, tree[node*2+1].scmax, tree[node*2].suff_sum + tree[node*2+1].pref_sum});
}
}
void update(int node, int st, int dr, int poz, int val) {
if (st == dr)
tree[node].sum = tree[node].pref_sum = tree[node].scmax = tree[node].suff_sum = val, v[st] = val;
else {
int mij = (st + dr) / 2;
if (poz <= mij)
update(node*2, st, mij, poz, val);
if (poz > mij)
update(node*2+1, mij+1, dr, poz, val);
tree[node].sum = tree[node*2].sum + tree[node*2+1].sum;
tree[node].pref_sum = max(tree[node*2].pref_sum, tree[node*2].sum + tree[node*2+1].pref_sum);
tree[node].suff_sum = max(tree[node*2+1].suff_sum, tree[node*2+1].sum + tree[node*2].suff_sum);
tree[node].scmax = max({tree[node*2].scmax, tree[node*2+1].scmax, tree[node*2].suff_sum + tree[node*2+1].pref_sum});
}
}
nod query(int node, int st, int dr, int left, int right) {
if (left <= st && dr <= right)
return tree[node];
else {
int mij = (st + dr) / 2;
if (left > mij)
return query(node*2+1, mij+1, dr, left, right);
else if (right <= mij)
return query(node*2, st, mij, left, right);
else {
nod stanga = query(node*2, st, mij, left, right);
nod dreapta = query(node*2+1, mij+1, dr, left, right);
return mergee(stanga, dreapta);
}
}
}
signed main()
{
freopen("maxq.in", "r", stdin);
freopen("maxq.out", "w", stdout);
cin.tie(0)->sync_with_stdio(false);
cin >> n >> m;
for (int i = 1; i <= n; i++)
cin >> v[i];
build(1, 1, n);
for (int i = 1; i <= m; i++) {
int st, dr;
cin >> st >> dr;
cout << query(1, 1, n, st, dr).scmax << '\n';
}
return 0;
}