#pragma GCC optimize("Ofast,inline,unroll-loops")
#include <bits/stdc++.h>
#define NMAX 100005
using namespace std;
ifstream fin("sequencequery.in");
ofstream fout("sequencequery.out");
long long v[NMAX];
struct arbint{
    long long s,smax,sl,sr;
};
int ok;
arbint aint[4 * NMAX],rez;
void init(arbint &a, const arbint &b){
    a.smax = b.smax;
    a.s = b.s;
    a.sl = b.sl;
    a.sr = b.sr;
}
arbint segmmax(const arbint &a, const arbint &b){
    arbint r;
    r.s = a.s + b.s;
    r.sl = max(a.sl, a.s + b.sl);
    r.sr = max(b.sr, b.s + a.sr);
    r.smax = max(max(b.smax, a.smax), b.sl + a.sr);
    return r;
}
void build(int nod, int st, int dr){
    if(st == dr){
        aint[nod].s = aint[nod].smax = aint[nod].sl = aint[nod].sr = v[st];
        return;
    }
    int med = (st + dr) / 2;
    build(2 * nod, st, med);
    build(2 * nod + 1, med + 1, dr);
    aint[nod].s = aint[2 * nod].s + aint[2 * nod + 1].s;
    aint[nod].sl = max(aint[2 * nod].sl, aint[2 * nod].s + aint[2 * nod + 1].sl);
    aint[nod].sr = max(aint[2 * nod + 1].sr, aint[2 * nod + 1].s + aint[2 * nod].sr);
    aint[nod].smax = max(max(aint[2 * nod].smax, aint[2 * nod + 1].smax), aint[2 * nod].sr + aint[2 * nod + 1].sl);
}
void query(int nod, int st, int dr, int qst, int qdr){
    if(qst <= st && dr <= qdr){
        if(!ok){
            init(rez,aint[nod]);
            ok = 1;
        }
        else rez = segmmax(rez,aint[nod]);
        return;
    }
    int med = (st + dr) / 2;
    if(qst <= med) query(2 * nod,st,med,qst,qdr);
    if(qdr >= med + 1) query(2 * nod + 1,med + 1,dr,qst,qdr);
}

int main()
{
    int n,i,j,k,st,dr;
    fin >> n >> k;
    for(i = 1; i <= n; i++) fin >> v[i];
    build(1,1,n);
    for(i = 1; i <= k; i++){
        fin >> st >> dr;
        ok = 0;
        query(1,1,n,st,dr);
        fout << rez.smax << "\n";
    }
    return 0;
}