#include<stdio.h>
#define Max 100000
#define max(a,b) ((a)>(b))? (a):(b)
FILE*f=fopen("sequencequery.in","r");
FILE*g=fopen("sequencequery.out","w");
int smax[3*Max+2], s[3*Max+2], sleft[3*Max+2], sright[3*Max+2];
int a[Max],n,m, v[Max], vf;
void update(int node, int l, int r)
{
if(l>r) return ;
if(l==r)
{
s[node]=smax[node]=sright[node]=sleft[node]=a[r];
return;
}
int m=(l+r)/2;
update(2*node,l,m);
update(2*node+1,m+1,r);
int fs=2*node, fd=2*node+1;
s[node]=s[fs]+s[fd];
sleft[node]=max( sleft[fs], s[fs]+sleft[fd] );
sright[node]=max ( sright[fd], s[fd] + sright[fs] );
smax[node]=max(s[node], sleft[node]);
smax[node]=max(smax[node], sright[node]);
smax[node]=max(smax[node], smax[fs]);
smax[node]=max(smax[node], smax[fd]);
smax[node]=max(smax[node], sleft[fd]+sright[fs]);
}
void query(int node, int l, int r, int i, int j)
{
if(i<=l && r<=j)
{
v[++vf]=node;
return;
}
int m=(r+l)/2;
if(i<=m) query(2*node, l, m, i, j);
if(j>m) query(2*node+1, m+1, r, i, j);
}
int suma()
{
int p,i, sum, su;
sum=smax[v[1]];
for(i=2;i<=vf; ++i)
{
su=0;
sum=max(sum, smax[v[i]]);
for(p=i-1; p>=1; --p)
{
sum=max(sum, sleft[v[i]]+sright[v[p]]+su);
sum=max(sum, s[v[i]]+s[v[p]]+su);
sum=max(sum, s[v[p]] + sleft[v[i]]+su);
sum=max(sum, sright[v[p]]+s[v[i]]+su );
su+=s[p];
}
}
return sum;
}
int main()
{
fscanf(f,"%d%d",&n,&m);
int i,x,y;
for(i=1;i<=n;++i) fscanf(f,"%d",&a[i]);
update(1,1,n);
while(m--)
{
fscanf(f,"%d%d",&x,&y);
vf=0;
query(1,1,n,x,y);
fprintf(g,"%d\n",suma());
}
return 0;
}