#include <fstream>

using namespace std;
int a[1000001],m,ok,p1,t,p2,s,st,j,poz,dr,i,smax=0,max1,n;
int main()
{ifstream f("sequencequery.in");
ofstream g("sequencequery.out");
  f>>n>>m;

    for(i=1;i<=n;i++)f>>a[i];

 for(i=1;i<=m;i++)
 {f>>p1>>p2;
max1=0;
s=0;
  ok=0;
  for(j=p1;j<=p2;j++)
    if(a[j]>0)ok=1;

    if(ok==0){max1=-9999999;for(j=p1;j<=p2;j++)if(a[j]>max1)max1=a[j];}
  else
  {for(j=p1;j<=p2;j++)
   {s=s+a[j];
    if(s>max1)max1=s;
    if(s<0)s=0;

   }
  }
   g<<max1<<'\n';
 }
    return 0;
}