#include <stdio.h>

#define NMAX 100002
#define INF 2305843009213693952

struct idk {
    long long int prefix;
    long long int sufix;
    long long int ssm;
    long long int sum;
};

int v[NMAX];
idk aint[4*NMAX];

long long int max(long long int a, long long int b) {
    if (a>b) {
        return a;
    }
    return b;
}

void combine (idk &rez, idk &a, idk &b) {
    rez.sum = a.sum+b.sum;
    rez.prefix = max(a.prefix, a.sum+b.prefix);
    rez.sufix = max(b.sufix, a.sufix+b.sum);
    rez.ssm = max(a.ssm, b.ssm);
    rez.ssm = max(rez.ssm, a.sufix+b.prefix);
}

void build(int nod, int st, int dr) {
    int mijl, fiust, fiudr;
    
    if (st == dr) {
        aint[nod].sum = v[st];
        aint[nod].sufix = aint[nod].ssm = aint[nod].prefix = aint[nod].sum;
        return;
    }
    
    mijl = (st+dr)/2;
    fiust = nod+1;
    fiudr = nod + 2*(mijl-st+1);
    
    build(fiust, st, mijl);
    build(fiudr, mijl+1, dr);
    
    combine(aint[nod], aint[fiust], aint[fiudr]);
}

void query(int nod, int st, int dr, int qst, int qdr, idk &rez) {
    int mijl, fiust, fiudr;
    idk rezst, rezdr;
    
    if (qst<=st && qdr>=dr) {
        rez = aint[nod];
    } else {
        mijl = (st+dr)/2;
        fiust = nod+1;
        fiudr = nod + 2*(mijl-st+1);
        
        rezst.prefix = rezst.sufix = rezst.ssm = -INF;
        rezst.sum = 0;
        rezdr.prefix = rezdr.sufix = rezdr.ssm = -INF;
        rezdr.sum = 0;
        if (qst<=mijl) {
            query(fiust, st, mijl, qst, qdr, rezst);
        }
        if (mijl<qdr) {
            query(fiudr, mijl+1, dr, qst, qdr, rezdr);
        }
        combine(rez, rezst, rezdr);
    }
}

int main() {
    FILE *fin, *fout;
    fin = fopen("sequencequery.in", "r");
    fout = fopen("sequencequery.out", "w");
    
    int n, t, tt, i, a, b;
    long long int r;
    idk rez;
    
    fscanf(fin, "%d%d", &n, &t);
    for (i=0; i<n; i++) {
        fscanf(fin, "%d", &v[i]);
    }
    build(0, 0, n-1);
    
    for (tt=0; tt<t; tt++) {
        fscanf(fin, "%d%d", &a, &b);
        a--;
        b--;
        rez.ssm = rez.sum = rez.prefix = rez.sufix = 0;
        query(0, 0, n-1, a, b, rez);
        r = rez.ssm;
        fprintf(fout, "%lld\n", r);
    }
    
    fclose(fin);
    fclose(fout);
    return 0;
}