#include <stdio.h>

#define maxn 100100
#define maxx 262144
#define maxv -100000000000LL
#define ll long long

int n,m,l,px,py;
int a[maxn];
ll sum[maxx],max[maxx],st[maxx],dr[maxx];

void query(int p,int r,int nod,ll &sol,ll &x,ll &y,ll &s)
{
     if ((px<=p) && (r<=py))
     {
         sol=max[nod];
         x=st[nod];
         y=dr[nod];
         s=sum[nod];
     }
     else {
			   int q=(p+r)/2;
               ll aux1=maxv,aux2=maxv,aux3=maxv,aux4=0;
               
               if (px<=q) query(p,q,nod*2,sol,x,aux3,s);
               if (q<py) query(q+1,r,nod*2+1,aux1,aux2,y,aux4);
               
               if (aux1>sol) sol=aux1;
               if (aux3+aux2>sol) sol=aux3+aux2;
               if (s+aux2>x) x=s+aux2;
               if (aux4+aux3>y) y=aux4+aux3;
               s=s+aux4;
          }
}

int main()
{
    freopen("sequencequery.in","r",stdin);
    freopen("sequencequery.out","w",stdout);
    
    scanf("%d %d ",&n,&m);
    int aux=n,i;
    ll x,y,sol,s;
    
    for (i=1;i<=n;i++) scanf("%d ",&a[i]);
    
    l=1;
    while (aux>0)
    {
       l<<=1;
       aux>>=1;
    }
        
    for (i=l;i<l+n;i++) 
    {
        max[i]=a[i-l+1];
        sum[i]=a[i-l+1];
        st[i]=a[i-l+1];
        dr[i]=a[i-l+1];
    }
    
    for (i=l-1;i>0;i--)
    {
        sum[i]=sum[i*2]+sum[i*2+1];
        max[i]=max[i*2];
        if (max[i*2+1]>max[i]) max[i]=max[i*2+1];
        if (dr[i*2]+st[i*2+1]>max[i]) max[i]=dr[i*2]+st[i*2+1];
        st[i]=st[i*2];
        if (sum[i*2]+st[i*2+1]>st[i]) st[i]=sum[i*2]+st[i*2+1];
        dr[i]=dr[i*2+1];
        if (sum[i*2+1]+dr[i*2]>dr[i]) dr[i]=sum[i*2+1]+dr[i*2];
    }
    
    for (i=1;i<=m;i++)
    {
        scanf("%d %d",&px,&py);

		s=0;
		x=maxv;
		sol=maxv;
		y=maxv;
		query(1,l,1,sol,x,y,s);
        printf("%lld\n",sol);
    }
    
    return 0;
}