#include<fstream>
#define MAXN 100001
#define INF 1000001
using namespace std;
typedef int var;
ifstream fin("sequencequery.in");
ofstream fout("sequencequery.out");
var n;
inline var zeros(const var &i) {
return (i&(-i));
}
var SUM[MAXN];
void add(var ind, var val) {
for(; ind <= n; ind += zeros(ind)) {
SUM[ind] += val;
}
}
var findsum(var ind) {
var s=0;
for(;ind;ind -= zeros(ind)) {
s+=SUM[ind];
}
return s;
}
var findelem(var ind) {
return findsum(ind) - findsum(ind-1);
}
var MAX[2*MAXN], BEG[2*MAXN], END[2*MAXN];
struct Trip {
var b, m, e;
Trip(var a, var d, var c) {
b = a; m = d; e = c;
}
};
void build(var node, var b, var e) {
if(b==e) {
BEG[node] = findelem(b);
END[node] = BEG[node];
MAX[node] = BEG[node];
}
else {
var m = (b+e)/2;
build(node*2, b, m);
build(node*2+1, m+1, e);
BEG[node] = BEG[node*2+1] + findsum(m) - findsum(b-1);
BEG[node] = max(BEG[node*2], BEG[node]);
END[node] = END[node*2] + findsum(e) - findsum(m);
END[node] = max(END[node], END[node*2+1]);
MAX[node] = max(MAX[node*2], MAX[node*2+1]);
MAX[node] = max(MAX[node], END[node*2] + BEG[node*2+1]);
}
}
Trip query(var node, var b, var e, var l, var r) {
if(b>r || e<l) return Trip(-INF, -INF, -INF);
if(b>=l && e<=r) return Trip(BEG[node], MAX[node], END[node]);
else {
var m = (b+e)/2;
Trip t1 = query(node*2, b, m, l, r);
Trip t2 = query(node*2+1, m+1, e, l, r);
var B, E, M;
B = t2.b + findsum(m) - findsum(b-1);
B = max(B, t1.b);
E = t1.e + findsum(e) - findsum(m);
E = max(E, t2.e);
M = max(t1.m, t2.m);
M = max(M, t1.e+t2.b);
return Trip(B, M, E);
}
}
int main() {
var m;
fin>>n>>m;
var B, E, M;
var a, b;
for(var i=1; i<=n; i++) {
fin>>a;
add(i, a);
}
build(1, 1, n);
while(m--) {
fin>>a>>b;
Trip t=query(1, 1, n, a, b);
fout<<t.m<<'\n';
}
return 0;
}