#include <iostream>
#include <stdio.h>

using namespace std;

#define MAXN 100000
#define RADICALMAXN 400
#define MINVAL -100000

int v[MAXN], batog2[RADICALMAXN][RADICALMAXN];

struct bat{
  int smax, smaxif, smaxil, smaxa;
};
bat batog[RADICALMAXN * (RADICALMAXN + 1)];

int main()/// problema este la smaxil!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
{
    FILE *fin, *fout;
    bat s, max;
    int n, q, i, j, st, dr, intst, intdr, maxoa, add;
    fin = fopen("sequencequery.in", "r");
    fscanf(fin, "%d%d", &n, &q);
    for(i = 0; i < n; i++){
      fscanf(fin, "%d", &v[i]);
    }

    for(i = 0; i < (RADICALMAXN * RADICALMAXN); i++){
      batog[i].smax = MINVAL;
    }
    for(i = 0; i < n; i += RADICALMAXN){
      s = {MINVAL, 0, 0, 0};
      max = {MINVAL, MINVAL, MINVAL, MINVAL};
      for(j = i; j < n; j++){
        if((s.smax + v[j]) < v[j]){
          s.smax = v[j];
        }else{
          s.smax += v[j];
        }
        if(max.smax < s.smax){
          max.smax = s.smax;
        }
        s.smaxif += v[j];
        if(max.smaxif < s.smaxif){
          max.smaxif = s.smaxif;
        }
        s.smaxa += v[j];
        if((j % RADICALMAXN) == (RADICALMAXN - 1)){
          batog[j / RADICALMAXN + i].smax = max.smax;
          batog[j / RADICALMAXN + i].smaxif = max.smaxif;
          batog[j / RADICALMAXN + i].smaxa = s.smaxa;
        }
      }
      if((j % RADICALMAXN) != 0){
        batog[j / RADICALMAXN + i].smax = max.smax;
        batog[j / RADICALMAXN + i].smaxif = max.smaxif;
        batog[j / RADICALMAXN + i].smaxa = s.smaxa;
      }
      if(i == 0){
        j = n - 1;
      }else{
        j = ((n - 1 - i) / RADICALMAXN + 1) * RADICALMAXN - 1;
      }
      for(; 0 <= j; j--){
        s.smaxil += v[j];
        if(max.smaxil < s.smaxil){
          max.smaxil = s.smaxil;
        }
        if((j % RADICALMAXN) == 0){///------------------------------------------------
          batog2[j / RADICALMAXN][(n - 1 - i) / RADICALMAXN] = max.smaxil;
        }
      }
    }

    fout = fopen("sequencequery.out", "w");
    for(i = 0; i < q; i++){
      fscanf(fin, "%d%d", &st, &dr);
      st--;
      dr--;
      if(0 < st){
        intst = ((st - 1) / RADICALMAXN + 1) * RADICALMAXN - 1;
        add = 1;
      }else{
        intst = 0;
        add = 0;
      }
      intdr = (dr / RADICALMAXN) * RADICALMAXN - 1;
      if(intst < intdr){
        s = {MINVAL, 0, 0, 0};
        max = {MINVAL, MINVAL, MINVAL, MINVAL};
        for(j = intst; st <= j; j--){
          if((s.smax + v[j]) < v[j]){
            s.smax = v[j];
          }else{
            s.smax += v[j];
          }
          if(max.smax < s.smax){
            max.smax = s.smax;
          }
          s.smaxil += v[j];
          if(max.smaxil < s.smaxil){
            max.smaxil = s.smaxil;
          }
        }
        maxoa = batog[intst + add + intdr / RADICALMAXN].smax;
        if(maxoa < max.smax){
          maxoa = max.smax;
        }
        if(maxoa < (max.smaxil + batog[intst + add + intdr / RADICALMAXN].smaxif)){
          maxoa = max.smaxil + batog[intst + add + intdr / RADICALMAXN].smaxif;
        }
        s.smax = MINVAL;
        max.smax = MINVAL;
        for(j = intdr + 1; j <= dr; j++){
          if((s.smax + v[j]) < v[j]){
            s.smax = v[j];
          }else{
            s.smax += v[j];
          }
          if(max.smax < s.smax){
            max.smax = s.smax;
          }
          s.smaxif += v[j];
          if(max.smaxif < s.smaxif){
            max.smaxif = s.smaxif;
          }
        }
        if(maxoa < max.smax){
          maxoa = max.smax;
        }
        if(maxoa < (max.smaxif + batog2[(intst + 1) / RADICALMAXN][intdr / RADICALMAXN])){
          maxoa = max.smaxif + batog2[(intst + 1) / RADICALMAXN][intdr / RADICALMAXN];
        }
        if(maxoa < (max.smaxif + batog[intst + add + intdr / RADICALMAXN].smaxa + max.smaxil)){
          maxoa = max.smaxif + batog[intst + add + intdr / RADICALMAXN].smaxa + max.smaxil;
        }
      }else{
        s.smax = maxoa = MINVAL;
        for(j = st; j <= dr; j++){
          if((s.smax + v[j]) < v[j]){
            s.smax = v[j];
          }else{
            s.smax += v[j];
          }
          if(maxoa < s.smax){
            maxoa = s.smax;
          }
        }
      }
      fprintf(fout, "%d\n", maxoa);
    }
    fclose(fin);
    fclose(fout);
    return 0;
}