#include <bits/stdc++.h>

using namespace std;

const int MAXN = 1e5;

#define ll long long

struct node {
  int l; int r; ll sum;
};


node seg[4 * MAXN + 1];

int a[MAXN + 1];
ll s[MAXN + 1];
void build (int st, int dr, int nod) {
  if (st == dr) {
    seg[nod].l = st;
    seg[nod].r = dr;
    seg[nod].sum = a[st];
    return;
  }
  int mij = (st + dr) / 2;
  build (st, mij, nod * 2);
  build (mij + 1, dr, nod * 2 + 1);
  if (s[seg[nod * 2 + 1].r] - s[seg[nod * 2].l - 1] >= max (seg[nod * 2].sum, seg[nod * 2 + 1].sum)) {
    seg[nod].sum = s[seg[nod * 2 + 1].r] - s[seg[nod * 2].l - 1];
    seg[nod].l = seg[2 * nod].l;
    seg[nod].r = seg[2 * nod + 1].r;
  }
  else {
    if (seg[nod * 2].sum > seg[nod * 2 + 1].sum) {
      seg[nod] = seg[nod * 2];
    }
    else
      seg[nod] = seg[nod * 2 + 1];
  }
}
const int INF = 1e9;

ll smax;
int lll, rrr;

void query (int st, int dr, int nod, int x, int y) {
  if (x <= st && dr <= y) {
    if (smax == -INF) {
      smax = seg[nod].sum;
      lll = seg[nod].l;
      rrr = seg[nod].r;
      return;
    }
    int left = min (lll, seg[nod].l);
    int right = max (rrr, seg[nod].r);
    if (s[right] - s[left - 1] > smax) {
      smax = s[right] - s[left - 1];
      lll = left;
      rrr = right;
      return;
    }
    if (seg[nod].sum > smax) {
      smax = seg[nod].sum;
      lll = seg[nod].l;
      rrr = seg[nod].r;
      return;
    }
    return;
  }
  int mij = (st + dr) / 2;
  if (x <= mij)
    query (st, mij, nod * 2, x, y);
  if (y > mij)
    query (mij + 1, dr, nod * 2 + 1, x, y);
}


int main() {
  int n, q, i, x, y;

  freopen ("sequencequery.in", "r", stdin);
  freopen ("sequencequery.out", "w", stdout);

  scanf ("%d%d", &n, &q);

  for (i = 1; i <= n; i++) {
    scanf ("%d", &a[i]);
    s[i] = s[i - 1] + a[i];
  }

  build (1, n, 1);

  while (q--) {
    scanf ("%d%d", &x, &y);
    smax = -INF;
    query (1, n, 1, x, y);
    printf ("%lld\n", smax);
  }

  return 0;
}