#include<stdio.h>


long long a[100005], n, m, x, y;

void suma(int p, int u)
{
  long long sc, max, i;
  sc=max=a[p];
  for (i=p+1; i<=u; i++)
    {
      if (sc<0) sc=a[i];
	else sc+=a[i];
      if (sc>max) max=sc;
    }
  printf("%lld\n",max);
}

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