#include <fstream.h>
int *T = new int[100000];
int *x = new int[100000];
int *y = new int[100000];
unsigned int n, m, i, j;
long sumamax, sumac, sfarsit, inceput, pozincep;
int
main ()
{
  ifstream f ("sequencequery.in");
  ofstream g ("sequencequery.out");
  f >> n >> m;
  for (i = 1; i <= n; ++i)
    f >> T[i];
  for (i = 1; i <= m; ++i)
    {
      f >> x[i] >> y[i];
      sumamax = T[x[i]];
      sumac = sumamax;
      pozincep = x[i];
      sfarsit = x[i];
      for (j = x[i] + 1; j <= y[i]; ++j)
        {
          if (sumac < 0)
            {
              sumac = T[j];
              pozincep = j;
            }
          else
            sumac += T[j];
          if (sumac > sumamax)
            {
              sumamax = sumac;
              inceput = pozincep;
              sfarsit = j;
            }
        }
      g << sumamax << '\n';
    }
  f.close ();
  g.close ();
  return 0;
}