#include <iostream.h>
#include <fstream.h>

long n,m,i,j,*v;

fstream f("sequencequery.in",ios::in), g("sequencequery.out",ios::out);

void secventa(int x,int y)
{long s1=-100001,s2; 
for(i=x;i<=y;i++) 
{s2=0;
for(j=i;j<=y;j++) {s2+=v[j]; if(s2>s1) s1=s2;} }
g<<s1<<endl;}

int main()
{f>>n; f>>m;
v=new long[n+1]; 
for(i=1;i<=n;i++)
f>>v[i];

while( !f.eof() )
{f>>n; f>>m;
secventa(n,m);}
f.close(); g.close();}