#include <stdio.h>

using namespace std;

#define MAXN 100000
#define MINS -1000000000

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

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

int calcMax(int a, int b, int c){
  int res, i, v[3];
  v[0] = a;
  v[1] = b;
  v[2] = c;

  res = v[0];
  for ( i = 1; i < 3; i++ ) {
    if ( res < v[i] )
      res = v[i];
  }

  return res;
}

void build(int left, int right, int loc) {
  int leftSon, rightSon, mid, i, maxpost, maxsuf, spost, ssuf;

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

  maxpost = spost = v[right];
  maxsuf = ssuf = v[left];
  for ( i = 1; i + left <= right; i++ ) {
    ssuf += v[i + left];
    spost += v[right - i];

    if ( ssuf > maxsuf )
      maxsuf = ssuf;
    if ( spost > maxpost )
      maxpost = spost;
  }
  aint[loc].sum = ssuf;
  aint[loc].postmax = maxpost;
  aint[loc].sufmax = maxsuf;

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

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

  aint[loc].ssm = calcMax(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 = calcMax(leftMax.ssm, rightMax.ssm, leftMax.postmax + rightMax.sufmax);
  res.postmax = calcMax(rightMax.postmax, leftMax.postmax + rightMax.sum, MINS);
  res.sufmax = calcMax(leftMax.sufmax, leftMax.sum + rightMax.sufmax, MINS);
  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, "%d\n", calcAns(0, n - 1, 0).ssm);
  }

  fclose(fin);
  fclose(fout);

  return 0;
}