#include <iostream>
#include <stdio.h>
#define NMAX 100000

using namespace std;

long long v[NMAX];
struct arb {
  long long sum, spref, ssuf, smax;
} aint[2*NMAX];

inline int mid( int l, int r ) { return ( l + r ) / 2; }
inline int leftSon( int node ) { return node + 1; }
inline int rightSon( int node, int m, int l ) { return node + 2 * ( m - l + 1 ); }

arb attr( arb lson, arb rson ) {
  arb x;

  x.sum = lson.sum + rson.sum;

  x.spref = max( lson.spref, lson.sum + rson.spref );
  x.ssuf = max( rson.ssuf, rson.sum + lson.ssuf );

  x.smax = max( x.sum, x.spref );
  x.smax = max( x.smax, x.ssuf );
  x.smax = max( x.smax, lson.smax );
  x.smax = max( x.smax, rson.smax );
  x.smax = max( x.smax, lson.ssuf + rson.spref );

  return x;
}

void build( int node, int l, int r ) {
  if( l == r ) {
    aint[node].sum = aint[node].spref = aint[node].ssuf = aint[node].smax = v[l];
    return;
  }
  int m = mid( l, r );
  int lson = leftSon( node );
  int rson = rightSon( node, m, l );

  build( lson, l, m );
  build( rson, m + 1, r );

  aint[node] = attr( aint[lson], aint[rson] );
}

arb query( int node, int l, int r, int a, int b ) {
  if( a <= l && r <= b ) {
      return aint[node];
  }

  int m = mid( l, r );
  int lson = leftSon( node );
  int rson = rightSon( node, m, l );


  if( b <= m )
    return query( lson, l, m, a, b );
  if( m < a )
    return query( rson, m + 1, r, a, b );

  arb left = query( lson, l, m, a, b );
  arb right = query( rson, m + 1, r, a, b );

  return attr( left, right );

}

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