#include <iostream>
#include <fstream>
using namespace std;
ifstream in("squencequery.in");
ofstream out("squencequery.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;
} 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;

}