#include <fstream>

using namespace std;

ifstream cin("sequencequery.in");
ofstream cout("sequencequery.out");

struct info {
  long long s, st, dr, mx;
}aint[500000];

int v[100001];

void build(int nod, int ls, int rs) {
  if (ls == rs) {
    aint[nod].s = aint[nod].st = aint[nod].dr = aint[nod].mx = v[ls];
  } else {
    build(2 * nod + 1, ls, (ls + rs) / 2);
    build(2 * nod + 2, (ls + rs) / 2 + 1, rs);
    aint[nod].s = aint[2 * nod + 1].s + aint[2 * nod + 2].s;
    aint[nod].st = max(aint[2 * nod + 1].st, aint[2 * nod + 1].s + aint[2 * nod + 2].st);
    aint[nod].dr = max(aint[2 * nod + 2].dr, aint[2 * nod + 2].s + aint[2 * nod + 1].dr);
    aint[nod].mx = max(max(aint[2 * nod + 1].mx, aint[2 * nod + 2].mx), aint[2 * nod + 1].dr + aint[2 * nod + 2].st);
  }
}
info query(int nod, int st, int dr, int a, int b) {
  info ans = {
    0,
    0,
    0,
    0
  };
  if (a <= st && dr <= b) {
    return aint[nod];
  } else {
    int mid = (st + dr) / 2;
    info ls, rs;
    int ok1 = 0, ok2 = 0;
    if (a <= mid) {
      ls = query(2 * nod + 1, st, mid, a, b);
      ok1 = 1;
    }
    if (b > mid) {
      rs = query(2 * nod + 2, mid + 1, dr, a, b);
      ok2 = 1;
    }
    if (ok1 == 1 && ok2 == 1) {
      ans.s = rs.s + ls.s;
      ans.st = max(ls.st, ls.s + rs.st);
      ans.dr = max(rs.dr, rs.s + ls.dr);
      ans.mx = max(max(ls.mx, rs.mx), ls.dr + ls.st);
    } else if (ok1 == 1) {
      ans = ls;
    } else if (ok2 == 1) ans = rs;
    return ans;
  }
}
int main() {
  int n, m, a, b;
  cin >> n >> m;
  for (int i = 1; i <= n; i++) cin >> v[i];
  build(0, 1, n);
  for (int i = 0; i < m; i++) {
    cin >> a >> b;
    info ans;
    ans = query(0, 1, n, a, b);
    cout << ans.mx << '\n';
  }
}