#include <fstream.h>
int *T=new int[100000];
int *x=new int[100000];
int *y=new int[100000];
int *summx=new int[100000];
unsigned int n, m, i, j;
long sumamax, sumac, aux1, aux2, sfarsit, inceput, pozincep; 
int main()
{
ifstream f("sequencequery.in");
ofstream g("sequencequery.out");
f>>n>>m;
for(i=1; i<=n; i++)
    f>>T[i];
for(i=1; i<=m; i++)
    {f>>x[i]>>y[i];}
for(i=1; i<=m; i++)
   {aux1=x[i]; aux2=y[i];
   sumamax=T[aux1];
   sumac=sumamax;
   pozincep=aux1;
   sfarsit=aux1;
   for(j=aux1+1; j<=aux2; j++)
       {if(sumac<0)
       {sumac=T[j];
	pozincep=j;
       }
     else
       sumac+=T[j];
    if(sumac>sumamax)
      {sumamax=sumac;
       inceput=pozincep;
       sfarsit=j;
      }
    }
   summx[i]=sumamax;
   }
for(i=1; i<=m; i++)
   g<<summx[i]<<endl;
f.close();
g.close();
return 0;
}