#include <fstream>
#include <algorithm>
 
using namespace std;
 
ifstream fin( "sequencequery.in" );
ofstream fout( "sequencequery.out" );

const int MaxN = 100001;
const long long Inf = 1e10;

struct segNode {
  long long pref, suff, ssm, sum;
} tree[4 * MaxN];

int v[MaxN];
 
static inline int left( int node ) {
  return (node << 1);
}
static inline int right( int node ) {
  return (node << 1) | 1;
}
 
static inline void fix( int node ) {
  tree[node].sum = tree[left( node )].sum + tree[right( node )].sum;
  tree[node].pref = max( tree[left( node )].pref, tree[left( node )].sum + tree[right( node )].pref );
  tree[node].suff = max( tree[right( node )].suff, tree[right( node )].sum + tree[left( node )].suff );
  tree[node].ssm = max( max( tree[left( node )].ssm, tree[right( node )].ssm ), tree[left( node )].suff + tree[right( node )].pref );
}
 
void build( int node, int st, int dr ) {
  int mij = (st + dr) / 2;
 
  if ( st == dr ) {
	tree[node].sum = tree[node].pref = tree[node].suff = tree[node].ssm = v[st];
	return;
  }
  build( left( node ), st, mij );
  build( right( node ), mij + 1, dr );
  fix( node );
}
 
long long sol, sol_pref;
 
void query( int node, int st, int dr, int x, int y ) {
  int mij = (st + dr) / 2;
  long long cp;
 
  if ( x <= st && dr <= y ) {
	cp = sol_pref;
	sol_pref = max( sol_pref + tree[node].sum, tree[node].suff );
	sol = max( max( sol, tree[node].ssm ), cp + tree[node].pref );
	return;
  }
  if ( x <= mij ) {
    query( left( node ), st, mij, x, y ); 
  }
  if ( y > mij ) {
	query( right( node ), mij + 1, dr, x, y );
  }
}
 
int main() {
  int n, i, m, a, b;
 
  fin >> n >> m;
  for ( i = 1; i <= n; ++i ) {
	fin >> v[i];
  }
  build( 1, 1, n );
  while ( m-- ) {
	fin >> a >> b;
	query( 1, 1, n, a, b );
	fout << sol << "\n";
	sol = sol_pref = -Inf;
  }
  fin.close();
  fout.close();
  return 0;
}