#include <stdio.h>
#define MAXNOD 262144
#define MAXN 100000
#define INF 2000000000
typedef struct{
  int max, st, dr;
}arb;

arb itv[MAXNOD + 1];
int sump[MAXN + 1];

inline int min2(int a, int b){
  return a < b ? a : b;
}

inline int max2(int a, int b){
  return a > b ? a : b;
}

inline int max3(int a, int b, int c){
  return max2(max2(a, b), c);
}

inline int sum(int x, int y){
  return sump[y] - sump[x - 1];
}

void update(int p, int st, int dr){
  if(st == dr){
    if(sum(st, st) < 0)
      itv[p].st = itv[p].dr = 0;
    else
      itv[p].st = itv[p].dr = 1;
    itv[p].max = sum(st, st);
  }
  else{
    int m = (st + dr) / 2;
    update(p * 2, st, m);
    update(p * 2 + 1, m + 1, dr);

    itv[p].st = itv[2 * p].st;
    if(itv[p].st == m - st + 1)
      itv[p].st += itv[2 * p + 1].st;
    else  if(sum(st, m + itv[2 * p + 1].st) > sum(st, st + itv[2 * p].st - min2(1, itv[2 * p].st)))
        itv[p].st = m - st + 1 + itv[2 * p + 1].st;

    itv[p].dr = itv[2 * p + 1].dr;
    if(itv[p].dr == dr - m)
      itv[p].dr += itv[2 * p].dr;
    else  if(sum(m - itv[2 * p].dr + 1, dr) > sum(dr - itv[2 * p - 1].dr + min2(1, itv[2 * p - 1].dr), dr))
        itv[p].dr = dr - m + itv[2 * p].dr;

    itv[p].max = max3(itv[2 * p].max, itv[2 * p + 1].max, sum(m - itv[2 * p].dr + 1, m + itv[2 * p + 1].st));
  }
}

int qdr(int p, int st, int dr, int x){   //dr = y
  if(st == x)
    return itv[p].dr;
  int m = (st + dr) / 2, rez;
  if(x > m)
    return qdr(2 * p + 1, m + 1, dr, x);
  rez = itv[2 * p + 1].dr;
  if(dr - m == rez)
    rez += qdr(2 * p, st, m, x);
  return rez;
}

int qst(int p, int st, int dr, int y){   //st = x
  if(dr == y)
    return itv[p].st;
  int m = (st + dr) / 2, rez;
  if(y <= m)
    return qst(2 * p, st, m, y);
  rez = itv[2 * p].st;
  if(m - st + 1 == rez)
    rez += qst(2 * p + 1, m + 1, dr, y);
  return rez;
}

int query(int p, int st, int dr, int x, int y){
  if(st == x && dr == y)
    return itv[p].max;
  int m = (st + dr) / 2;
  if(m >= y)
    return query(2 * p, st, m, x, y);
  if(m < x)
    return query(2 * p + 1, m + 1, dr, x, y);
  return max3(query(2 * p, st, m, x, m), query(2 * p + 1, m + 1, dr, m + 1, y),
              sum(m - qdr(2 * p, st, m, x) + 1, m + qst(2 * p + 1, m + 1, dr, y)));
}

int main(){
  FILE *in = fopen("sequencequery.in", "r");
  int n, m, i, x, y;
  fscanf(in, "%d%d", &n, &m);
  for(i = 1; i <= n; i++){
    fscanf(in, "%d", &sump[i]);
    sump[i] += sump[i - 1];
  }
  update(1, 1, n);
  FILE *out = fopen("sequencequery.out", "w");
  for(i = 0; i < m; i++){
    fscanf(in, "%d%d", &x, &y);
    fprintf(out, "%d\n", query(1, 1, n, x, y));
  }
  fclose(in);
  fclose(out);
  return 0;
}