#include <bits/stdc++.h>
#define maxn 100000
#define maxl2 17
#define pii pair<int,int>
#define fi first
#define se second
#define inf INT_MAX/2-1

using namespace std;

struct yes
{
  pii cap;
  int vmax;
};

int v[maxn+5], lpos[maxn+5];
yes aint[(1<<(maxl2+2))+5];
int ans;

void build ( int p, pii itv )
{
  if ( itv.fi == itv.se )
  {
    aint[p].cap = itv;
    aint[p].vmax = v[itv.fi];
    lpos[itv.fi] = p;
    return;
  }
  int mid = (itv.fi+itv.se)/2;
  build ( p*2, {itv.fi,mid} );
  build ( p*2+1, {mid+1,itv.se} );
  if ( aint[p*2].vmax > aint[p*2+1].vmax )
    aint[p] = aint[p*2];
  else aint[p] = aint[p*2+1];
  if ( aint[p*2].cap.se + 1 == aint[p*2+1].cap.fi && aint[p].vmax < aint[p*2].vmax + aint[p*2+1].vmax )
    aint[p] = { {aint[p*2].cap.fi,aint[p*2+1].cap.se}, aint[p*2].vmax + aint[p*2+1].vmax };
}

int main ()
{
  ifstream fin ( "sequencequery.in" );
  ofstream fout ( "sequencequery.out" );

  int n, m; fin >> n >> m;

  int i, x, y, p, cur;
  for ( i = 1; i <= n; i++ ) fin >> v[i];
  build ( 1, {1,n} );

  while (m--)
  {
    fin >> x >> y; cur = 0; ans = -inf;
    while ( x <= y )
    {
      p = lpos[x];
      while ( p/2 >= 1 && aint[p/2].cap.fi == x && aint[p/2].cap.se <= y ) p /= 2;
      cur += aint[p].vmax; ans = max (ans,cur); cur = max (cur,0);
      x = aint[p].cap.se + 1;
    }
    fout << ans << '\n';
  }

  fin.close ();
  fout.close ();

  return 0;
}