#include<stdio.h>

#define X 100001

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

int main()
{
 freopen("sequencequery.in","r",stdin);
 freopen("sequencequery.out","w",stdout);
 long x,y,a[X],n,m,i;
 scanf("%ld%ld",&n,&m);
 for(i=1; i<=n; ++i) scanf("%ld",&a[i]);
 for(; m; --m)
 {
  scanf("%ld%ld",&x,&y);
  printf("%ld\n",sum(x,y,a));
 }
 return 0;
}