#include <fstream>
#include <algorithm>

#define NMAX 100000

using namespace std;

struct nod {
  long long sum, prefSsm, sufSsm, ssm;
}aux;

nod aint[NMAX * 4 + 1];

int elem[131073];

void buildArb(int p, int lInt, int rInt) {
  if (lInt == rInt) {
    aint[p].sum = elem[lInt];
    aint[p].prefSsm = aint[p].sum;
    aint[p].sufSsm = aint[p].sum;
    aint[p].ssm = aint[p].sum;
    return;
  }
  int leftChild = p * 2, rightChild = p * 2 + 1;
  buildArb(leftChild, lInt, lInt + (rInt - lInt) / 2);
  buildArb(rightChild, lInt + (rInt - lInt) / 2 + 1, rInt);
  aint[p].sum = aint[leftChild].sum + aint[rightChild].sum;
  aint[p].prefSsm = max(aint[leftChild].prefSsm, aint[leftChild].sum + aint[rightChild].prefSsm);
  aint[p].sufSsm = max(aint[rightChild].sufSsm, aint[rightChild].sum + aint[leftChild].sufSsm);
  aint[p].ssm = max(aint[leftChild].sufSsm + aint[rightChild].prefSsm, max(aint[leftChild].ssm, aint[rightChild].ssm));
}

void query(int p, int lInt, int rInt, int lExtr, int rExtr) {
  if (lExtr <= lInt && rInt <= rExtr) {
    aux.ssm = max(aux.sufSsm + aint[p].prefSsm, max(aux.ssm, aint[p].ssm));
    aux.prefSsm = max(aux.prefSsm, aux.sum + aint[p].prefSsm);
    aux.sufSsm = max(aint[p].sufSsm, aint[p].sum + aux.sufSsm);
    aux.sum += aint[p].sum;
    return;
  }
  int leftChild = p * 2, rightChild = p * 2 + 1;
  if((lInt <= lExtr && lExtr <= lInt + (rInt - lInt) / 2) || (lInt <= rExtr && rExtr <= lInt + (rInt - lInt) / 2))
   query(leftChild, lInt, lInt + (rInt - lInt) / 2, lExtr, rExtr);
  if ((lInt + (rInt - lInt) / 2 + 1 <= lExtr && lExtr <= rInt) || (lInt + (rInt - lInt) / 2 + 1 <= rExtr && rExtr <= rInt))
   query(rightChild, lInt + (rInt - lInt) / 2 + 1, rInt, lExtr, rExtr);
}

signed main() {
  ifstream cin("sequencequery.in");
  ofstream cout("sequencequery.out");
  int n, m, put2, i, a, b;
  cin >> n;
  cin >> m;
  put2 = 1;
  while (put2 < n)
    put2 *= 2;
  for (i = 1; i <= n; i++) {
    cin >> elem[i];
  }
  buildArb(1, 1, put2);
  for (i = 1; i <= m; i++) {
    cin >> a >> b;
    aux.sum = 0;
    aux.ssm = (LLONG_MAX - 100000 ) * (-1);
    aux.prefSsm = (LLONG_MAX - 100000) * (-1);
    aux.sufSsm = (LLONG_MAX - 100000) * (-1);
    query(1, 1, put2, a, b);
    cout << aux.ssm << "\n";
  }
  return 0;
}