#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;
i=1;
while(i<=n)
    {f>>T[i]; i++;}
i=1;
while(i<=m)
    {f>>x[i]>>y[i];
    i++;}
i=1;
while(i<=m)
   {//aux1=x[i]; aux2=y[i];
   sumamax=T[x[i]];
   sumac=sumamax;
   pozincep=x[i];
   sfarsit=x[i];
   j=x[i]+1;
   while(j<=y[i])
      {if(sumac<0)
       {sumac=T[j];
	pozincep=j;
       }
     else
       sumac+=T[j];
    if(sumac>sumamax)
      {sumamax=sumac;
       inceput=pozincep;
       sfarsit=j;
      }
    j++;}
   summx[i]=sumamax;
   i++;}
for(i=1; i<=m; i++)
   g<<summx[i]<<"\n";
f.close();
g.close();
return 0;
}