#include <stdio.h>
#include <iostream>

using namespace std;

#define MAXN 100000
#define MINS -1000000000

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

int v[MAXN];
data aint[4 * MAXN];
int limLeft, limRight;

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

  if (left == right) {
    aint[loc].postmax = aint[loc].sufmax = aint[loc].s = 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].s = max(max(aint[leftSon].s, aint[rightSon].s), aint[leftSon].postmax + aint[rightSon].sufmax);
}


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

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

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

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

  if (limLeft <= mid) {
    leftMax = calc(left, mid, leftSon);
  }
  if (limRight > mid) {
    rightMax = calc(mid + 1, right, rightSon);
  }

  res.s = max(max(leftMax.s, rightMax.s), 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;
  int n, m, a, b, i;

  fin = fopen("sequencequery.in", "r");
  fout = fopen("sequencequery.out", "w");

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

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

  build(0, n - 1, 0);

  for (i = m; i > 0; i--) {
    fscanf(fin, "%d%d", &a, &b);
    a--;
    b--;

    limLeft = a;
    limRight = b;
    fprintf(fout, "%lld\n", calc(0, n - 1, 0).s);
  }

  fclose(fin);
  fclose(fout);

  return 0;
}