#include <cstdio>
#include <algorithm>
using namespace std;
const int N=100005;
struct nod{
long long s,st,dr,best;
} v[4*N],aux;
bool sem;
nod Union(nod a, nod b){
nod c;
c.s=a.s+b.s;
c.st=max(a.st, a.s+b.st);
c.dr=max(b.dr, b.s+a.dr);
c.best=max( max( max(a.best, b.best), max(c.st, c.dr) ), a.dr+b.st);
return c;
}
void update(int pos, int st, int dr, int a, long long val){
if(st>a) return;
if(dr<a) return;
if(st==dr){
v[pos].s=val;
v[pos].st=val;
v[pos].dr=val;
v[pos].best=val;
return;
}
update(2*pos, st, (st+dr)/2, a, val);
update(2*pos+1, (st+dr)/2+1, dr, a, val);
v[pos]=Union(v[2*pos],v[2*pos+1]);
}
void query(int pos, int st, int dr, int a, int b){
if(st>b) return;
if(dr<a) return;
if(a<=st and dr<=b){
if(sem==0) sem=1, aux=v[pos];
else aux=Union(aux, v[pos]);
return;
}
query(2*pos, st, (st+dr)/2, a, b);
query(2*pos+1, (st+dr)/2+1, dr, a, b);
}
int main(){
freopen("sequencequery.in","r",stdin);
freopen("sequencequery.out","w",stdout);
int n,m,i,x,a,b;
scanf("%d%d",&n,&m);
for(i=1;i<=n;i++){
scanf("%d",&x);
update(1,1,n,i,1ll*x);
}
for(i=1;i<=m;i++){
scanf("%d%d",&a,&b);
sem=0;
query(1,1,n,a,b);
printf("%lld\n",aux.best);
}
return 0;
}