#include <cstdio>
#define DN 400005
#define LL long long
LL a[DN],b[DN],c[DN],d[DN],sum,rez;
inline LL max(LL x,LL y) { return x>y ? x:y; }
void update(int vn, int ls, int ld,int val,int poz) {
if(ls==ld) {
a[vn]=b[vn]=c[vn]=val;
d[vn]=val;
return;
}
int m=(ls+ld)>>1,fs=vn<<1;
if(poz<=m) update(fs,ls,m,val,poz);
else update(fs+1,m+1,ld,val,poz);
a[vn]=max(a[fs],d[fs]+a[fs+1]);
b[vn]=max(b[fs]+d[fs+1],b[fs+1]);
c[vn]=max(max(c[fs],c[fs+1]),b[fs]+a[fs+1]);
d[vn]=d[fs]+d[fs+1];
}
void query(int vn, int ls, int ld,int gls, int gld) {
if(ls==ld) {
rez=max(rez,max(sum+a[vn],c[vn]));
sum=max(sum+d[vn],b[vn]);
return;
}
int m=(ls+ld)>>1,fs=vn<<1;
if(gls<=m) query(fs,ls,m,gls,gld);
if(gld>m) query(fs+1,m+1,ld,gls,gld);
}
int main()
{
int n,m,gls,gld,v[DN];
freopen("sequencequery.in","r",stdin);
freopen("sequencequery.out","w",stdout);
scanf("%d %d",&n,&m);
for(int i=1; i<=n; ++i) {
scanf("%d",&v[i]);
update(1,1,n,v[i],i);
}
for(int i=1; i<=m; ++i) {
sum=0;
rez=-9999999999LL;
scanf("%d %d",&gls,&gld);
query(1,1,n,gls,gld);
printf("%lld\n",rez);
}
return 0;
}