#include<stdio.h>
int a[100001],st[400001],mm,p1,p2,i,n,dr[400001],rint[400001],tot[400001],sol,maxim,S;
int max(int q1,int q2)
{
if (q1>q2) return q1;
return q2;
}
void inita(int nod,int b, int e)
{
   if (b==e) {st[nod]=dr[nod]=tot[nod]=rint[nod]=a[b];return;}
     else
       {
       inita(2*nod,b,(b+e)/2);
       inita(2*nod+1,(b+e)/2+1,e);
       st[nod]=max(st[2*nod],tot[2*nod]+st[2*nod+1]);
       dr[nod]=max(dr[2*nod+1],tot[2*nod+1]+dr[2*nod]);
       rint[nod]=max(max(rint[2*nod],rint[2*nod+1]),dr[2*nod]+st[2*nod+1]);
       tot[nod]=tot[2*nod]+tot[2*nod+1];
       }
}
void query(int nod,int b,int e,int s,int d)
{
  int secvs,secvd;
     if (s<=b&&e<=d)     
        {
         maxim=max(max(S+st[nod],rint[nod]),maxim);
         S=max(S+tot[nod],dr[nod]);
         return;
        }
      else      
       {
       int mij=(b+e)/2;
       if (s<=mij) query(2*nod,b,(b+e)/2,s,d);
       if (mij<d)  query(2*nod+1,(b+e)/2+1,e,s,d);
       }
}
int main()
{
   freopen("sequencequery.in","r",stdin);
   freopen("sequencequery.out","w",stdout);
   scanf("%ld %ld",&n,&mm);
   for(i=1;i<=n;i++)
    scanf("%ld",&a[i]);
    inita(1,1,n);
   for(i=1;i<=mm;i++)
   {
    scanf("%ld %ld",&p1,&p2);
    S=0;
    maxim=a[p1];
    query(1,1,n,p1,p2);
    printf("%ld\n",maxim);
   }
   return 0;
}