#include<cstdio>
#include<algorithm>
using namespace std;
int n,m,i,a,b,R,SOL,V[100010];
struct tree
{
int val;
int left;
int right;
}arb[300010];
void read(),solve(),init(int,int,int,int,int),query(int,int,int,int,int);
int main()
{
read();
solve();
return 0;
}
void read()
{
freopen("sequencequery.in","r",stdin);
freopen("sequencequery.out","w",stdout);
scanf("%d%d",&n,&m);
for(i=1;i<=n;i++)
{
scanf("%d",&V[i]);
V[i]+=V[i-1];
init(1,1,n,i,V[i]-V[i-1]);
}
}
void solve()
{
for(;m--;)
{
scanf("%d%d",&a,&b);
SOL=-(1<<30);
R=SOL;
query(1,1,n,a,b);
printf("%d\n",SOL);
}
}
void init(int nod,int left,int right,int pos, int val)
{
if(pos<left || pos>right)return;
if(left==right)
{
arb[nod].val=val;
arb[nod].left=val;
arb[nod].right=val;
return ;
}
int mid=(left+right)/2;
init(nod*2,left,mid,pos,val);
init(nod*2+1,mid+1,right,pos,val);
arb[nod].val=max(arb[nod*2].val,max(arb[nod*2+1].val,arb[nod*2].right+arb[nod*2+1].left) );
arb[nod].left=max(arb[nod*2].left,V[mid]-V[left-1]+arb[nod*2+1].left);
arb[nod].right=max(arb[nod*2+1].right,V[right]-V[mid]+arb[nod*2].right);
}
void query(int nod,int left,int right,int a,int b)
{
if(a<=left && right<=b)
{
if(SOL< arb[nod].val)SOL=arb[nod].val;
if(SOL< R+arb[nod].left)SOL=R+arb[nod].left;
R=max(arb[nod].right,V[right]-V[left-1]+R);
return;
}
int mid=(left+right)/2;
if(a<=mid)query(nod*2,left,mid,a,b);
if(mid<b) query(nod*2+1,mid+1,right,a,b);
}