#include <iostream>
#include <fstream>
#include <queue>
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
{
  int pre = 0, suf = 0, sum = 0, val = 0, maxx = inf;
} d[nmax*4];
queue<nod> q;
void mer(nod* n1, nod* n2, nod* n3);
void build( int v, int st, int dr);
void 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;
    query(1, 1, n, st, dr);
    nod rez;
    while(!q.empty())
    {
      auto nr = q.front();
      q.pop();
      nod anew;
      mer(&anew, &rez, &nr);
      rez = anew;
    }
    if ( rez.val!=0)
    out << rez.val << "\n";
    else out << rez.maxx << "\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]);
}

void query(int v, int st, int dr, int str, int drr)
{

   if ( str>drr)
    return ;
   else if ( str == st and drr == dr )
   {
     q.emplace(d[v]);
     return;
   }
   int mij = (st + dr)/2;
   query(v*2, st, mij, str, min(mij, drr));
   query(v*2+1, mij+1, dr, max(mij+1, str), drr);

}