#include<stdio.h>

#define X 100001

long sum(long x, long y, long a[])
{
 long i,s=0,sbest=-X;
 for(i=x; i<=y; ++i)
 {
  if(s>=0) s+=a[i];
      else s=a[i];
  if(s>sbest) sbest=s;
 }
 return sbest;
}

int main()
{
 freopen("sequencequery.in","r",stdin);
 freopen("sequencequery.out","w",stdout);
 long poz=0,aux=0,x,y,a[X],n,m,i;
 char s[X*6];
 scanf("%ld%ld",&n,&m);
 gets(s); gets(s);
 for(i=0; s[i]; ++i)
   if(s[i]==' ') a[++poz]=aux,aux=0;
	    else aux=aux*10+s[i]-'0';
 a[++poz]=aux;

 for(; m; --m)
 {
  scanf("%ld%ld",&x,&y);
  printf("%ld\n",sum(x,y,a));
 }
 return 0;
}