#include <iostream>

#define NMAX 100000
#define INFINIT 100001

using namespace std;

struct Node {
  long long pref ;
  long long suf ;
  long long ssm ;
  long long s ;
};

struct Aint {
  Node aint [ 4 * NMAX + 1 ] ;
  Aint (long long n) {
    for (long long i = 0 ; i <= n ; i++ )
      this->aint[i] = {-INFINIT, -INFINIT, -INFINIT, -INFINIT} ;
  }
  Node join (Node node1, Node node2 ) {
    Node rez ;
    rez.s = node1.s + node2.s ;
    rez.ssm = max ( node1.suf + node2.pref, max(node1.ssm, node2.ssm)) ;
    rez.pref = max ( node1.s + node2.pref, node1.pref) ;
    rez.suf = max ( node2.suf, node2.s + node1.suf ) ;
    return rez ;
  }
  void update (long long node, long long st, long long dr, long long poz, long long val ) {
    if (poz < st || poz > dr )
      return ;
    else {
      if (st == dr )
        this->aint[node] = {val, val, val, val} ;
      else {
        long long mij = (st + dr ) / 2 ;
        update (2*node,   st, mij, poz, val ) ;
        update (2*node+1, mij+1, dr, poz, val ) ;
        aint[node] = join(this->aint[2*node], this->aint[2*node+1]) ;
      }
    }
  }
  Node query (long long node, long long st, long long dr, long long left, long long right) {
    if (right < st || left > dr )
      return {-INFINIT, -INFINIT, -INFINIT, -INFINIT} ;
    else {
      if (st >= left && dr <= right ) {
        return aint[node] ;
      }
      else {
        long long mij = ( st + dr ) / 2 ;
        return this->join(query(2 * node, st, mij, left, right), query(2*node+1, mij+1, dr, left, right)) ;
      }
    }
  }
};

long long v [ NMAX + 1 ] ;
Aint a(NMAX) ;

int main() {

  FILE *fin, *fout ;
  fin = fopen ("sequencequery.in", "r" ) ;
  fout = fopen ("sequencequery.out", "w" ) ;
  long long n, i, m, st, dr ;
  fscanf (fin, "%lld%lld", &n, &m ) ;
  for (i = 1 ; i <= n ; i++) {
    fscanf (fin, "%lld", &v[i] ) ;
    a.update(1, 1, n, i, v[i] ) ;
  }
  for (i = 1 ; i <= m ; i++ ) {
    fscanf (fin, "%lld%lld", &st, &dr ) ;
    fprintf (fout, "%lld\n", a.query(1, 1, n, st, dr).ssm ) ;
  }
  return 0;
}