#include <stdio.h>
#define DIM 270000

struct str{
  long long a;
  long long b;
  long long c;
  long long s;
};

int n,m;
long long A[DIM],B[DIM],C[DIM],S[DIM];

long long maxim(long long a, long long b){
  if (a>b) return a;
  else return b;
}

void update(int st, int dr, int nod, int poz, int val) {
  int mij;
  if ((st==poz) && (dr==poz)) {
    A[nod] = B[nod] = C[nod] = S[nod] = val;
  } else {
    mij = (st+dr)/2;
    if (poz<=mij)
      update(st,mij,2*nod,poz,val);
    if (poz>mij)
      update(mij+1,dr,2*nod+1,poz,val);
    A[nod] = maxim(A[2*nod],S[2*nod]+A[2*nod+1]);
    B[nod] = maxim(B[2*nod+1],S[2*nod+1]+B[2*nod]);
    C[nod] = maxim(maxim(C[2*nod],C[2*nod+1]),A[2*nod+1]+B[2*nod]);
    S[nod] = S[2*nod]+S[2*nod+1];
  }
}

str query(int st, int dr, int nod, int a, int b) {
  int mij,ok1,ok2;
  str r,rs,rd;
  if ((a<=st) && (dr<=b)){
    r.a = A[nod];
    r.b = B[nod];
    r.c = C[nod];
    r.s = S[nod];
    return r;
  } else {
    mij = (st+dr)/2;
    ok1 = 0;
    if (a<=mij) {
      rs = query(st, mij, 2*nod, a, b);
      ok1 = 1;
    }
    ok2 = 0;
    if (b>mij) {
      rd = query(mij+1,dr, 2*nod+1, a, b);
      ok2 = 1;
    }
    if (ok1 && ok2) {
      r.a = maxim(rs.a,rs.s+rd.a);
      r.b = maxim(rd.b,rd.s+rs.b);
      r.c = maxim(maxim(rs.c,rd.c),rs.b+rd.a);
      r.s = rs.s+rd.s;
      return r;
    } else if (ok1) {
      return rs;
    } else
      return rd;
  }
}


int main() {
  int val,poz,a,b,op,i;
  str r;
  FILE *f = fopen("sequencequery.in","r");;
  FILE *g = fopen("sequencequery.out","w");;

  fscanf(f,"%d %d",&n,&m);
  for (i=1;i<=n;i++) {
    fscanf(f,"%d",&val);
    update(1,n,1,i,val);
  }
  for (i=1;i<=m;i++) {
    fscanf(f,"%d %d",&a, &b);
    r = query(1,n,1,a,b);
//    if (r.c<0)
//      r.c = 0;
    fprintf(g,"%lld\n",r.c);
  }

  fclose(g);
  fclose(f);
  return 0;
}