#include <fstream.h>
#include <values.h>
long k,n,max=-MAXLONG,a[100010],xx,yy,in;
ifstream fin("sequencequery.in");
void citire(){
fin>>n>>k;
for (long i=0;i<n;i++)
  fin>>a[i];
}

int main(){
long aux;
citire();
ofstream fout("sequencequery.out");
for (long i=0;i<k;i++)             {
   fin>>xx>>yy;
   xx--;
   yy--;
   long S=0,maxx=-2346233,Maxim=-2341525;

   for (int i=xx;i<=yy;i++)
   {
      S+=a[i];
      if (a[i]>maxx)
	maxx=a[i];
      if (S<0)
	S=0;
	else
      if (S>Maxim)
	 Maxim=S;
   }
     if (Maxim>=0)
	 fout<<Maxim<<"\n";
     else
	fout<<maxx<<"\n";                   }
fin.close();
fout.close();
return 0;
}