#include <fstream.h>
#include <values.h>
long k,n,max=-MAXLONG,a[100009],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 maxim=0,aux;
citire();
ofstream fout("sequencequery.out");
for (long i=0;i<k;i++)             {
   fin>>xx>>yy;
   maxim=-124515;
   xx--;
   yy--;
   long S=0,maxx=-2346233;

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