#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;
    if ( x > y ) swap ( x, y ); ///zau bai
    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;

}