#include <cstdio>
using namespace std;
const int NMAX = 100005;
const int INF = 0x7fffffff;
long long int maxy(long long int a, long long int b) {
  if(a < b) {
    a = b;
  }
  return a;
}
struct SECV {
  long long int stotal;
  long long int sstart;
  long long int send;
  long long int smax;
};
SECV a[NMAX * 4];
void update(int st, int dr, int nod, int poz, long long int val) {
  if(st == dr) {
    a[nod].stotal = val;
    a[nod].sstart = val;
    a[nod].send = val;
    a[nod].smax = val;
    return ;
  }
  else {
    int mij = (st + dr) / 2;
    if(poz <= mij) {
      update(st, mij, nod * 2, poz, val);
    }
    else {
      update(mij + 1, dr, nod * 2 + 1, poz, val);
    }
    a[nod].stotal = a[nod * 2].stotal + a[nod * 2 + 1].stotal;
    a[nod].sstart = maxy(a[nod * 2].sstart, a[nod * 2].stotal + a[nod * 2 + 1].sstart);
    a[nod].sstart = maxy(a[nod].sstart, a[nod].stotal);
    a[nod].send = maxy(a[nod * 2 + 1].send, a[nod * 2 + 1].stotal + a[nod * 2].send);
    a[nod].send = maxy(a[nod].send, a[nod].stotal);
    a[nod].smax = maxy(a[nod * 2].smax, a[nod * 2 + 1].smax);
    a[nod].smax = maxy(a[nod].smax, a[nod * 2].send + a[nod * 2 + 1].sstart);
  }
}
long long int sol = 0, suma = 0;
void query(int x, int y, int st, int dr, int nod) {
  if(x <= st && dr <= y) {
    sol = maxy(sol, maxy(a[nod].smax, suma + a[nod].sstart));
    suma = maxy(suma + a[nod].stotal, a[nod].send);
  }
  else {
    int mij = (st + dr) / 2;
    if(x <= mij) {
      query(x, y, st, mij, nod * 2);
    }
    if(mij < y) {
      query(x, y, mij + 1, dr, nod * 2 + 1);
    }
  }
}

int main() {
  int n, m;
  freopen("sequencequery.in", "r", stdin);
  freopen("sequencequery.out", "w", stdout);
  scanf("%d%d", &n, &m);
  for(int i = 1; i <= n; ++i) {
    long long int val;
    scanf("%lld", &val);
    update(1, n, 1, i, val);
  }
  for(int i = 1; i <= m; ++i) {
    int x, y;
    scanf("%d%d", &x, &y);
    sol = -INF; suma = 0;
    query(x, y, 1, n, 1);
    printf("%lld\n", sol);
  }
  return 0;
}