#include <fstream>

using namespace std;

const int Nmax = 100000;

int v[Nmax];

struct arbore_intervale{
    int val;
    int prefix;
    int sufix;
    int sum;
};

arbore_intervale aint[4 * Nmax];

void build(int nod, int st, int dr){
    if(st == dr){
        aint[nod].val = v[st];
        aint[nod].prefix = v[st];
        aint[nod].sufix = v[st];
        aint[nod].sum = v[st];
        return;
    }

    int mid = (st + dr) / 2;
    int vecinSt = 2 * nod, vecinDr = 2 * nod + 1;

    build(vecinSt, st, mid);
    build(vecinDr, mid + 1, dr);

    aint[nod].val = max(aint[vecinSt].val, aint[vecinDr].val);
    aint[nod].val = max(aint[nod].val, aint[vecinSt].sufix + aint[vecinDr].prefix);

    aint[nod].sum = aint[vecinSt].sum + aint[vecinDr].sum;
    aint[nod].prefix = max(aint[vecinSt].prefix, aint[vecinSt].sum + aint[vecinDr].prefix);
    aint[nod].sufix = max(aint[vecinDr].sufix, aint[vecinDr].sum + aint[vecinSt].sufix);
}

arbore_intervale query(int nod, int st, int dr, int a, int b){
    if(st == a && dr == b){
        return aint[nod];
    }

    int mid = (st + dr) / 2;

    if(b <= mid){
        return query(2 * nod, st, mid, a, b);
    }
    else if(mid < a){
        return query(2 * nod + 1, mid + 1, dr, a, b);
    }
    else{
        arbore_intervale sol, vecinSt, vecinDr;

        vecinSt = query(2 * nod, st, mid, a, mid);
        vecinDr = query(2 * nod + 1, mid + 1, dr, mid + 1, b);

        sol.val = max(vecinSt.val, vecinDr.val);

        if(vecinSt.sufix + vecinDr.prefix >= sol.val){
            sol.val = vecinSt.sufix + vecinDr.prefix;
        }

        sol.sum = vecinSt.sum + vecinDr.sum;
        sol.prefix = max(vecinSt.prefix, vecinSt.sum + vecinDr.prefix);
        sol.sufix = max(vecinDr.sufix, vecinDr.sum + vecinSt.sufix);

        return sol;
    }
}

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

    int n, m, a, b;

    fin >> n >> m;
    for(int i = 0; i < n; i++){
        fin >> v[i];
    }

    build(1, 0, n - 1);

    for(int i = 0; i < m; i++){
        fin >> a >> b;
        a--; b--;

        fout << query(1, 0, n - 1, a, b).val << '\n';
    }
    return 0;
}