#include <iostream>

using namespace std;

#define MAXN 100000
#define MINS -1000000000

struct data{
  long long ssm, postmax, sufmax, sum;
};

int v[MAXN];
data aint[4 * MAXN];
int leftLim, rightLim;

void build(int left, int right, int loc) {
  int leftSon, rightSon, mid;

  if ( left == right ) {
    aint[loc].postmax = aint[loc].sufmax = aint[loc].ssm = aint[loc].sum = v[left];
    return;
  }

  mid = (left + right) / 2;
  leftSon = loc + 1;
  rightSon = loc + 2 * (mid - left + 1);

  build(left, mid, leftSon);
  build(mid + 1, right, rightSon);

  aint[loc].sum = aint[leftSon].sum + aint[rightSon].sum;
  aint[loc].postmax = max(aint[rightSon].postmax, aint[leftSon].postmax + aint[rightSon].sum);
  aint[loc].sufmax = max(aint[leftSon].sufmax, aint[leftSon].sum + aint[rightSon].sufmax);
  aint[loc].ssm = max(max(aint[leftSon].ssm, aint[rightSon].ssm), aint[leftSon].postmax + aint[rightSon].sufmax);
}


data calcAns(int left, int right, int loc) {
  int leftSon, rightSon, mid;
  data leftMax, rightMax, res;

  if ( leftLim <= left && right <= rightLim ) {
    return aint[loc];
  }

  mid = (left + right) / 2;
  leftSon = loc + 1;
  rightSon = loc + 2 * (mid - left + 1);

  leftMax.postmax = leftMax.sufmax = leftMax.ssm = MINS;
  leftMax.sum = 0;
  rightMax = leftMax;

  if ( leftLim <= mid ) {
    leftMax = calcAns(left, mid, leftSon);
  }
  if ( rightLim > mid ) {
    rightMax = calcAns(mid + 1, right, rightSon);
  }

  res.ssm = max(max(leftMax.ssm, rightMax.ssm), leftMax.postmax + rightMax.sufmax);
  res.postmax = max(rightMax.postmax, leftMax.postmax + rightMax.sum);
  res.sufmax = max(leftMax.sufmax, leftMax.sum + rightMax.sufmax);
  res.sum = leftMax.sum + rightMax.sum;

  return res;
}


int main() {
  FILE *fin, *fout;
  fin = fopen("sequencequery.in", "r");
  fout = fopen("sequencequery.out", "w");

  int n, m, a, b, i;

  fscanf(fin, "%d%d", &n, &m);

  for  ( i = 0; i < n; i++ )
    fscanf(fin, "%d", &v[i]);

  build(0, n - 1, 0);

  while ( m-- ) {
    fscanf(fin, "%d%d", &a, &b);
    a--;
    b--;

    leftLim = a;
    rightLim = b;
    fprintf(fout, "%lld\n", calcAns(0, n - 1, 0).ssm);
  }

  fclose(fin);
  fclose(fout);

  return 0;
}