#include <iostream>
using namespace std;
const int MAXN = 1e5;
const int MINVAL = -100001;
#define int long long

struct nod{
  int prefixmaxim;
  int sufixmaxim;
  int smax;
  int stotal;
};

int v[MAXN+1];
nod aint[2*MAXN+1];

nod combina( nod a, nod b ) {
  nod rez;
  rez.prefixmaxim = max( a.prefixmaxim, a.stotal + b.prefixmaxim );
  rez.sufixmaxim = max( b.sufixmaxim, b.stotal + a.sufixmaxim );
  rez.smax = max( max( a.smax, b.smax ), a.sufixmaxim + b.prefixmaxim );
  rez.stotal = a.stotal + b.stotal;
  return rez;
}

void build( int left, int right, int node ) {
  int mid, leftSon, rightSon;
  if( left == right ) {
    aint[node].stotal = aint[node].prefixmaxim = aint[node].sufixmaxim = aint[node].smax = v[left];
    return;
  }
  mid = ( left + right ) / 2;
  leftSon = node + 1;
  rightSon = node + 2 * ( mid - left + 1 );
  build( left, mid, leftSon );
  build( mid + 1, right, rightSon );
  aint[node] = combina( aint[leftSon], aint[rightSon] );
}

/* void update( int left, int right, int node, int x, int val ) {
  int mid;
  if( left == right ) {
    aint[node] -= val;
    return;
  }
  mid = ( left + right ) / 2;
  if( x <= mid )
    update( left, mid, node + 1, x, val );
  else
    update( mid + 1, right, node + 2 * ( mid - left + 1 ), x, val );
  aint[node] = aint[node+1] + aint[node+2*(mid-left+1)];
} */

nod query( int left, int right, int node, int qleft, int qright ) {
  int mid;
  if( qright < left || qleft > right ) {
    return { MINVAL, MINVAL, MINVAL, MINVAL };
  }
  if( left >= qleft && right <= qright ) {
    return aint[node];
  }
  mid = ( left + right ) / 2;
  nod s1 = { MINVAL, MINVAL, MINVAL, MINVAL }, s2 = { MINVAL, MINVAL, MINVAL, MINVAL };
  if( qleft <= mid )
    s1 = query( left, mid, node + 1, qleft, qright );
  if( mid < qright )
    s2 = query( mid + 1, right, node + 2 * ( mid - left + 1 ), qleft, qright );
  return combina(s1, s2);
}

signed main() {
  FILE *fin, *fout;
  int n, m, a, b, i;
  fin = fopen( "sequencequery.in", "r" );
  fout = fopen( "sequencequery.out", "w" );
  fscanf( fin, "%lld%lld", &n, &m );
  for( i = 1; i <= n; i++ )
    fscanf( fin, "%lld", &v[i] );
  build( 1, n, 1 );
  /* for( i = 1; i <= 2 * n; i++ )
    printf( "%d ", aint[i] ); */
  for( i = 0; i < m; i++ ) {
    fscanf( fin, "%lld%lld", &a, &b );
    fprintf( fout, "%lld\n", query( 1, n, 1, a, b ).smax );
  }
  fclose( fin );
  fclose( fout );
  return 0;
}