#include <iostream>
#include <fstream>
using namespace std;
ifstream in("sequencequery.in");
ofstream out("sequencequery.out");

constexpr int nmax = 100001;
const long long inf = -1000000000000000000;
long long a[nmax];
int n, m;

struct nod
{
  long long pre = 0, suf = 0, sum = 0, val = 0, maxx = inf;
} ;
nod d[nmax*4];

void mer(nod& n1, nod& n2, nod& n3);
void build( int v, int st, int dr);
nod query(int v, int st, int dr, int str, int drr);
int main()
{
   in >> n >> m;
   for ( int i = 1; i <= n; ++i )
    in >> a[i];
  build(1, 1, n);

  for ( int i = 1; i <= m; ++i )
  {
    int st, dr;
    in >> st >> dr;
    auto nr = query(1, 1, n, st, dr);
    if ( nr.val == 0 )
      out << nr.maxx << "\n";
    else out << nr.val << "\n";
  }
    return 0;
}

void mer(nod& n1, nod& n2, nod& n3)
{
  n1.sum = n2.sum + n3.sum;
  n1.val = max(max(n2.val, n3.val), n2.suf + n3.pre);
  n1.pre = max(n2.pre, n2.sum + n3.pre);
  n1.suf = max(n3.suf, n3.sum + n2.suf);
  n1.maxx = max(n2.maxx, n3.maxx);
}

void build( int v, int st, int dr)
{

  if ( st == dr )
  {
    d[v].sum = a[st];
    d[v].pre = max(1ll*0, a[st]);
    d[v].suf = max(1ll*0, a[st]);
    d[v].val = max(1ll*0, a[st]);
    d[v].maxx = a[st];
    return ;
  }
  int mij = (st + dr)/2;
  build(v*2, st, mij);
  build(v*2+1, mij+1, dr);
  mer(d[v], d[v*2], d[v*2+1]);
}

nod query(int v, int st, int dr, int str, int drr)
{
   nod nn;
   if ( str>drr)
    return nn;
   else if ( str == st and drr == dr )
    return d[v];
   int mij = (st + dr)/2;
   nod nn1 = query(v*2, st, mij, str, min(mij, drr));
   nod nn2 = query(v*2+1, mij+1, dr, max(mij+1, str), drr);
   mer(nn, nn1, nn2);
  return nn;

}