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

long maxim(long aa,long b){
max=-MAXLONG;
long S=0;
for (long i=aa;i<=b;i++){
   S=a[i];
   if (S>max)
     max=S;
     for (long j=i+1;j<=b;j++){
	 S+=a[j];
	 if (S>max)
	    max=S;}
     }
return max;
}
int main(){
citire();
ofstream fout("sequencequery.out");
for (long i=0;i<k;i++)             {
   fin>>x>>y;
   fout<<maxim(x-1,y-1);
   fout<<"\n";                   }
fin.close();
fout.close();
return 0;
}