#include <fstream>
#include <climits>
#define DIM 100005

using namespace std;

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

long long n, i, a, b, v[DIM], m, sol, s;

struct tetracloruraDeCarbon{
    long long all, ssm, sst, ddr;
} A[4*DIM];

inline void build (int nod, int st, int dr){
    int mid;
    if (st == dr){
        fin >> v[st];
        A[nod].ssm = v[st];
        A[nod].sst = v[st];
        A[nod].ddr = v[st];
        A[nod].all = v[st];
    }
    else{
        mid = st + (dr - st)/2;
        build (2*nod, st, mid);
        build (2*nod+1, mid+1, dr);
        A[nod].all = A[2*nod].all + A[2*nod+1].all;
        A[nod].ssm = max (A[2*nod].ssm, max (A[2*nod+1].ssm, A[2*nod].ddr + A[2*nod+1].sst));
        A[nod].sst = max (A[2*nod].sst, A[2*nod].all + A[2*nod+1].sst);
        A[nod].ddr = max (A[2*nod+1].ddr, A[2*nod].ddr + A[2*nod+1].all);
    }
}

inline void query (int nod, int st, int dr, int a, int b){
    int mid;
    if (a <= st && b >= dr){
        sol = max (A[nod].ssm, max (sol, s + A[nod].sst));
        s = max ((s + A[nod].all), A[nod].ddr);
        sol = max (sol, s);
    }
    else{
        mid = st + (dr - st)/2;
        if (a <= mid){
            query (2*nod, st, mid, a, b);
        }
        if (b > mid){
            query (2*nod+1, mid+1, dr, a, b);
        }
    }
}

int main(){
    fin >> n >> m;
    build (1, 1, n);
    for (i=1; i<=m; i++){
        fin >> a >> b;
        sol = INT_MIN, s = INT_MIN;
        query (1, 1, n, a, b);
        fout << sol << "\n";
    }
    return 0;
}