#include <bits/stdc++.h>

using namespace std;

ifstream fin("sequencequery.in");
ofstream fout("sequencequery.out");

const int OO = 100005;

int v[100005];

struct arb{
    int sumMax;
    int sumSt;
    int sumDr;
    int sumInt;
    arb(){
        sumSt = sumDr = sumMax = sumInt = -OO;
    }
    arb(int sumMax, int sumSt, int sumDr, int sumInt){
        this -> sumMax = sumMax;
        this -> sumSt = sumSt;
        this -> sumDr = sumDr;
        this -> sumInt = sumInt;

    }
} A[400005];

void build(int nod, int st, int dr){
    if(st == dr){
        A[nod].sumMax = A[nod].sumSt = A[nod].sumDr = A[nod].sumInt = v[st];
    }
    else{
        int mij = (st + dr) / 2;
        int nodSt = 2 * mij, nodDr = 2 * mij + 1;
        build(nodSt, st, mij);
        build(nodDr, mij + 1, dr);
        A[nod].sumMax = max(max(A[nodSt].sumMax, A[nodDr].sumMax), A[nodDr].sumSt + A[nodSt].sumDr);
        A[nod].sumSt = max(A[nodSt].sumSt, A[nodSt].sumInt + A[nodDr].sumSt);
        A[nod].sumDr = max(A[nodDr].sumDr, A[nodDr].sumInt + A[nodSt].sumDr);
        A[nod].sumInt = A[nodSt].sumInt + A[nodDr].sumInt;
    }
}

arb query(int nod, int st, int dr, int qst, int qdr){
    if(st >= qst && dr <= qdr){
        return A[nod];
    }
    else{
        int mij = (st + dr) / 2;
        int nodSt = 2 * mij, nodDr = 2 * mij + 1;
        arb q1, q2;
        if(qst <= mij){
            q1 = query(nodSt, st, mij, qst, qdr);
        }
        if(qdr > mij){
            q2 = query(nodDr, mij + 1, dr, qst, qdr);
        }
        arb qAns(max(max(q1.sumMax, q2.sumMax), q1.sumDr + q2.sumSt),
                 max(q1.sumSt, q1.sumInt + q2.sumSt),
                 max(q2.sumDr, q1.sumDr + q2.sumInt),
                 q1.sumInt + q2.sumInt
                 );
        return qAns;
    }
}

int main()
{
    int n, m;
    fin >> n >> m;
    for(int i=1; i<=n; i++){
        fin >> v[i];
    }
    build(1, 1, n);
    for(int a, b, i=1; i<=m; i++){
        fin >> a >> b;
        fout << query(1, 1, n, a, b).sumMax << '\n';
    }
    return 0;
}