#include <fstream>
using namespace std;
ifstream fin("sequencequery.in");
ofstream fout("sequencequery.out");
const int MAXN = 4e5 + 5;
long long aints[MAXN];
long long aintsm[MAXN];
long long aintl[MAXN] ;
long long aintr[MAXN];
long long ma,s;
void update(long long nod, long long l , long long r, long long poz, long long val) {
if(l == r) {
aintl[nod] = aintr[nod] = aints[nod] = aintsm[nod] = val;
return;
}
long long mj = (l + r) >> 1;
if(mj >= poz)
update(nod*2,l,mj,poz,val);
else
update(nod*2+1,mj+1,r,poz,val);
aints[nod] = aints[nod*2] + aints[nod*2+1];
aintsm[nod] = max(aintsm[nod*2],max(aintsm[nod*2+1],aintr[nod*2] + aintl[nod*2+1]));
aintl[nod]= max(aintl[nod*2],aints[nod*2] + aintl[nod*2+1]);
aintr[nod]= max(aintr[nod*2+1],aintr[nod*2+1] + aintr[nod*2]);
}
void query(long long nod, long long l, long long r, long long x, long long y){
if(l >= x and r <= y){
ma = max(ma,aintsm[nod]);
ma = max(ma,s + aintl[nod]);
s = max(s+aints[nod],aintr[nod]);
return;
}
long long mj = (l + r) >> 1;
if(x <= mj)
query(nod*2,l,mj,x,y);
if(y > mj)
query(nod*2+1,mj+1,r,x,y);
}
long long n,m,a[MAXN],x,y;
int main() {
fin >> n >> m;
for ( int i = 1; i <= n; ++i) {
fin >> a[i];
update(1,1,n,i,a[i]);
}
for ( int i = 1; i <= m; ++i) {
fin >> x >> y;
ma = - (1LL<<50);
s = 0;
query(1,1,n,x,y);
fout << ma << "\n";
}
}