#include <iostream>
#include <fstream>
#include <cstring>
#define inf 2147000000
using namespace std;
ifstream f("sequencequery.in");
ofstream g("sequencequery.out");
struct arbint
{ long long v,l,r,s; };
long long n,m,dp[100005],k,sol;
arbint a[400069];
void Update(int nod,int st,int dr,int ind,int x)
{ int mid=(st+dr)/2;
if (st==dr)
{ a[nod].v=a[nod].l=a[nod].r=a[nod].s=x; return;}
if (ind<=mid) Update(nod*2,st,mid,ind,x);
else Update(nod*2+1,mid+1,dr,ind,x);
a[nod].s= a[2*nod].s + a[2*nod+1].s;
a[nod].l= max(a[2*nod].l , a[2*nod].s + a[2*nod+1].l);
a[nod].r= max(a[2*nod+1].r, a[2*nod+1].s + a[2*nod].r);
a[nod].v= max(a[2*nod].v, max(a[2*nod+1].v , a[2*nod].r + a[2*nod+1].l));
}
void Query(int nod,int st,int dr,int x,int y)
{ int mid=(st+dr)/2;
if (x<=st && dr<=y)
{ k++;
dp[k]=max(a[nod].r,a[nod].s+dp[k-1]);
sol=max(sol,max(dp[k],dp[k-1]+a[nod].l));
sol=max(sol,a[nod].v);
}
else
{
if (st==dr) return;
if (x<=mid) Query(2*nod,st,mid,x,y);
if (y>mid) Query(2*nod+1,mid+1,dr,x,y);
}
}
int main()
{ int n,i,el,sx,sy;
f>>n>>m;
for(i=1;i<=n;i++)
{ f>>el;
Update(1,1,n,i,el);
}
for(i=1;i<=m;i++)
{ f>>sx>>sy;
k=0;
sol=-inf;
Query(1,1,n,sx,sy);
g<<sol<<"\n";
}
return 0;
}