#include <stdio.h>

#define FIN "sequencequery.in"
#define FOUT "sequencequery.out"
#define Nmax 1700000
#define nmax 100001
#define Inf 1<<25

#define FOR(i,a,b) for( i = (a); i<= (b); ++i )

#define Min(a,b) ( s[(a)] < s[(b)] ) ? (a) : b
#define Max(a,b) ( s[(a)] > s[(b)] ) ? (a) : b


typedef long long lint;


int min[Nmax], max[Nmax];
lint s[nmax];

int a, b, MIN, MAX;

void updateMax(int poz,int ind,int st,int dr)
 {
  if(st==dr)
   {
    max[ind]=poz;
   }
    else
   {
    int mij=(st+dr)>>1;

    if(poz<=mij)
     updateMax(poz,ind*2,st,mij);
      else
     updateMax(poz,ind*2+1,mij+1,dr);

    if(s[poz]>s[max[ind]])
     max[ind]=poz;
   }
 }

void queryMax(int ind, int st, int dr)
 {
  if(a<=st && dr<=b)
   {
    if(s[MAX]<s[max[ind]])
     MAX=max[ind];
   }
    else
   {
    int mij=(st+dr)>>1;

    if(a<=mij)
     queryMax(ind*2,st,mij);

    if(mij<b)
     queryMax(ind*2+1,mij+1,dr);
   }
 }


void updateMin(int poz,int ind,int st,int dr)
 {
  if(st==dr)
   {
    min[ind]=poz;
   }
    else
   {
    int mij=(st+dr)>>1;

    if(poz<=mij)
     updateMin(poz,ind*2,st,mij);
      else
     updateMin(poz,ind*2+1,mij+1,dr);

    if(s[poz]<s[min[ind]])
     min[ind]=poz;
   }
 }

void queryMin(int ind, int st, int dr)
 {
  if(a<=st && dr<=b)
   {
    if(s[MIN]>s[min[ind]])
     MIN=min[ind];
   }
    else
   {
    int mij=(st+dr)>>1;

    if(a<=mij)
     queryMin(ind*2,st,mij);

    if(mij<b)
     queryMin(ind*2+1,mij+1,dr);
   }
 }

int main()
 {
  freopen(FIN,"r",stdin);
  freopen(FOUT,"w",stdout);

  int i, n,m;
  lint x, MIN1, MAX1, SECV;

  scanf("%i%i", &n, &m);

  FOR(i,1,n)
   {
    scanf("%lld", &x);
    s[i]=s[i-1]+x;
    s[0]=Inf;
    updateMin(i,1,1,n);
    s[0]*=-1;
    updateMax(i,1,1,n);
   }

  FOR(i,1,m)
   {
    scanf("%i%i", &a, &b);
    MIN=a;
    queryMin(1,1,n);

    MAX=a;
    queryMax(1,1,n);

    
    if(MAX<MIN)
     {
      MIN1=MIN;
      MAX1=MAX;



      MIN=x=b;b=MAX;
      queryMin(1,1,n);

      if(MAX>MIN)
       SECV=s[MAX]-s[MIN];
        else
      if(MAX==MIN)
       SECV=s[MAX]-s[MAX-1];
    

      MAX=a=MIN1;b=x;
      queryMax(1,1,n);

      if( (SECV<s[MAX]-s[MIN]) && (MAX>MIN) )
       SECV=s[MAX]-s[MIN];
        else
      if( (MAX==MIN) && (SECV < s[MAX]-s[MAX-1]) )
       SECV=s[MAX]-s[MAX-1];
     }
      else
     if(MAX==MIN)
     SECV=s[MAX]-s[MAX-1];
      else
     SECV=s[MAX]-s[MIN];

    printf("%lld\n", SECV);
   }

  
  return 0;
 }