#include<fstream>
using namespace std;

ifstream in("maxq.in");
ofstream out("maxq.out");

const int N = 300100;
const long long inf = (long long)1<<59;

long long n, a[3*N], b[3*N], s[3*N], c[3*N], qq, poz, val, el[N], px, py, maxs, ant;

inline int max(const long long &a, const long long &b) {return a > b ? a : b;}

void makeArb(const int &nod, const int &pozx, const int &pozy) {
    if(pozx == pozy) {
        a[nod] = b[nod] = c[nod] = s[nod] = el[pozx];
        return;
    }

    int mid = (pozx + pozy)>>1;

    makeArb(2*nod, pozx, mid);
    makeArb(2*nod + 1, mid + 1, pozy);

    s[nod] = s[2*nod] + s[2*nod + 1];
    a[nod] = max(a[2*nod], s[2*nod] + a[2*nod + 1]);
    b[nod] = max(b[2*nod + 1], s[2*nod + 1] + b[2*nod]);
    c[nod] = max(c[2*nod], max(c[2*nod + 1], b[2*nod] + a[2*nod + 1]));
}

void update(const int &nod, const int &pozx, const int &pozy) {
    if(pozx == pozy) {
        a[nod] = b[nod] = c[nod] = s[nod] = val;
        return;
    }

    int mid = (pozx + pozy)>>1;

    if(mid >= poz)
        update(2*nod, pozx, mid);
    else
        update(2*nod + 1, mid + 1, pozy);

    s[nod] = s[2*nod] + s[2*nod + 1];
    a[nod] = max(a[2*nod], s[2*nod] + a[2*nod + 1]);
    b[nod] = max(b[2*nod + 1], s[2*nod + 1] + b[2*nod]);
    c[nod] = max(c[2*nod], max(c[2*nod + 1], b[2*nod] + a[2*nod + 1]));
}

void q(const int &nod, const int &pozx, const int &pozy) {

    if(pozx >= px && pozy <= py) {

        maxs = max(maxs, max(c[nod], a[nod] + ant));
        ant = max(b[nod], ant + s[nod]);

        return;
    }

    int mid = (pozx + pozy)>>1;

    if(mid >= px)
        q(2*nod, pozx, mid);
    if(mid < py)
        q(2*nod + 1, mid + 1, pozy);
}

int main() {
    int i, op;

    in >> n >> qq;

    for(i = 1; i<=n; ++i)
        in >> el[i];
    makeArb(1, 1, n);

    //in >> qq;

    for(i = 1; i<=qq; ++i) {

        //in >> op;

        //if(op) {
            in >> px >> py; px++; py++;

            ant = 0;
            maxs = -inf;
            q(1, 1, n);

            out << maxs << "\n";
        /*}
        else {
            in >> poz >> val; ++poz;

            update(1, 1, n);
        }*/
    }
    return 0;
}