#include<cstdio>
#include<utility>

#define MAX_SIZE 1<<20
#define max(a,b) ((a)>(b)?(a):(b))
#define lf (2*node)
#define rf (2*node+1)

FILE *f=fopen("sequencequery.in","r");
FILE *g=fopen("sequencequery.out","w");

using namespace std;

template <class T>

	class aint
{
public:
    int ff,ss,th,ft;
};

int n,v[MAX_SIZE],pos,st,dr;
long long val;
long long Answer,S;
aint < long long > arb[MAX_SIZE<<1+1];

void Build( int node, int left, int right )
{
    if(left == right )
    {
        arb[node].ff=arb[node].ss=arb[node].th=v[left];
        arb[node].ft=v[left];
    }
    else

    {
        int mid =(left+right)>>1;
        Build(lf,left,mid);
        Build(rf,mid+1,right);

        arb[node].ff=max(arb[lf].ff,arb[rf].ff+arb[lf].ft);
        arb[node].ss=max(arb[rf].ss,arb[lf].ss+arb[rf].ft);
        arb[node].th=max(arb[lf].ss+arb[rf].ff,max(arb[lf].th,arb[rf].th));
  
		arb[node].ft=arb[lf].ft+arb[rf].ft;


    }


}/*
void Update(int node,int left,int right)
{
  if( left == right )
  {
      arb[node].ft=val;
      arb[node].ff=arb[node].ss=arb[node].th=val;
  }
  else
  {
      int mid=(left+right)>>1;
      if(pos <= mid)
        Update(lf,left,mid);
      else
        Update(rf,mid+1,right);

        arb[node].ff=max(arb[lf].ff,arb[rf].ff+arb[lf].ft);
        arb[node].ss=max(arb[rf].ss,arb[lf].ss+arb[rf].ft);
        arb[node].th=max(arb[lf].ss+arb[rf].ff,max(arb[lf].th,arb[rf].th));
  
		arb[node].ft=arb[lf].ft+arb[rf].ft;

 }
}
*/
void Query (int node, int left ,int right )
{
    if( st <= left && right  <= dr )
    {
		
		Answer=max(Answer,max(arb[node].th,S+arb[node].ff));
          S=max(S+arb[node].ft,arb[node].ss);


    }
    else
    {
        int mid=(left+right)>>1;
        if(st<= mid)
            Query(lf,left,mid);
        if(dr>mid)
            Query(rf,mid+1,right);


    }





}


int main( void )
{
	int m;
    fscanf(f,"%d%d",&n,&m);
    for(int i(1);  i <= n; ++i )
    {
        fscanf(f,"%d",&v[i]);
		
	}
    Build(1,1,n);
    for(int i(1); i <= m ; ++i )
    {
        int x,y;
        fscanf(f,"%d%d",&x,&y);
      
            S=0;
			Answer=-1<<30;
            st=x;
            dr=y;
            Query(1,1,n);
			fprintf(g,"%lld\n",Answer);
		 


    }

   fclose(f);
   fclose(g);
   return 0;


}