#include <cstdio>

struct elem {
  long long sum, ssm, inc, sfa;
};

const int N = 100005;

elem rc, ai[4 * N];

int n, q;

long long MIN;

inline long long max(long long x, long long y) {
  return x < y ? y : x;
}

void edit(elem &rez, elem a, elem b) {
  rez.sum = a.sum + b.sum;
  rez.ssm = max(a.sfa + b.sum, max(a.sum + b.inc, max(a.sfa + b.inc, max(a.ssm, b.ssm))));
  rez.inc = max(a.inc, a.sum + b.inc);
  rez.sfa = max(b.sfa, b.sum + a.sfa);
}

void update(int nod, int p, int u, int poz, int val) {
  if (p == u) {
    ai[nod].sum = val;
    ai[nod].ssm = val;
    ai[nod].inc = val;
    ai[nod].sfa = val;
    return ;
  }
  int m = (p + u) / 2;
  if (m < poz)
    update(2 * nod + 1, m + 1, u, poz, val);
  else
    update(2 * nod, p, m, poz, val);
  edit(ai[nod], ai[2 * nod], ai[2 * nod + 1]);
}

void read() {
  int x;
  freopen("sequencequery.in", "r", stdin);
  freopen("sequencequery.out", "w", stdout);

  scanf("%d %d", &n, &q);
  for (int i = 1; i <= n; ++ i) {
    scanf("%d", &x);
    update(1, 1, n, i, x);
  }
}

void query(int nod, int p, int u, int x, int y) {
  if (p > y || u < x)
    return;
  if (x <= p && u <= y) {
    if (rc.ssm == MIN) {
      rc.sum = ai[nod].sum;
      rc.ssm = ai[nod].ssm;
      rc.inc = ai[nod].inc;
      rc.sfa = ai[nod].sfa;
      return;
    }
    edit(rc, rc, ai[nod]);
    return;
  }
  if (p == u)
    return;
  int m = (p + u) / 2;
  query(2 * nod, p, m, x, y);
  query(2 * nod + 1, m + 1, u, x, y);
}

void solve() {
  int x, y;
  for (int i = 1; i <= q; ++ i) {
    scanf("%d %d", &x, &y);
    rc.sum = rc.ssm = rc.inc = rc.sfa = MIN;
    query(1, 1, n, x, y);
    printf("%lld\n", rc.ssm);
  }
}

void init() {
  MIN -= 100000;
  MIN *= 100000;
  MIN -= 2;
}

int main() {
  read();
  init();
  solve();
  return 0;
}