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

using namespace std;

struct yes
{
  lll ssm, pref, suff, sum;
};

yes aint[maxn*4+5];
int v[maxn+5];

yes unite ( yes a, yes b )
{
  yes c;
  c.sum = a.sum + b.sum;
  c.pref = max (a.pref,b.pref+a.sum);
  c.suff = max (b.suff,a.suff+b.sum);
  c.ssm = max ( max(a.ssm,b.ssm), a.suff + b.pref );
  return c;
}

void build ( int p, pii itv )
{
  if ( itv.fi == itv.se )
  {
    lll x = v[itv.fi] * 1LL;
    aint[p] = {x,x,x,x};
    return;
  }
  int mid = (itv.fi + itv.se) / 2;
  build ( p*2, {itv.fi,mid} );
  build ( p*2+1, {mid+1,itv.se} );
  aint[p] = unite (aint[p*2],aint[p*2+1]);
}

yes query ( int p, pii itv, pii ok )
{
  yes x;
  if ( itv.fi > ok.se || ok.fi > itv.se ) { x = {-inf,-inf,-inf,-inf}; return x; }
  if ( itv.fi >= ok.fi && itv.se <= ok.se ) { return aint[p]; }
  int mid = (itv.fi + itv.se) / 2;
  yes a = query ( p*2, {itv.fi, mid}, ok );
  yes b = query ( p*2+1, {mid+1,itv.se}, ok );
  if ( a.pref == -inf ) return b;
  if ( b.pref == -inf ) return a;
  x = unite (a,b);
  return x;
}

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

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

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

  while (m--)
  {
    fin >> x >> y;
    fout << query ( 1, {1,n}, {x,y} ).ssm << '\n';
  }

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

  return 0;
}