#include <iostream>
#include <fstream>
#define MAX 200002
using namespace std;
int n,m,t,x,y;

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

int max(int a, int b, int c){
    return max(a, max(b, c));
}

struct nod{
    int sum;
    int suf;
    int pref;
    int ssm;
};

nod operator + (const nod &st, const nod &dr){
    nod ans;
    ans.sum = st.sum+dr.sum;
    ans.pref = max(st.pref, st.sum+dr.pref);
    ans.suf = max(dr.suf, dr.sum+st.suf);
    ans.ssm = max(st.ssm, dr.ssm, st.suf+dr.pref);
    return ans;
}

nod aint[4*MAX];

void build(int nod, int st, int dr){
    if(st == dr){
        fin >> x;
        aint[nod] = {x, x, x, x};
    }else{
        int mid = (st+dr)/2;
        build(2*nod, st, mid);
        build(2*nod+1, mid+1, dr);
        aint[nod] = aint[2*nod]+aint[2*nod+1];
    }
}

nod query(int nod, int st, int dr, int a, int b){
    if(a <= st && dr <= b){
        return aint[nod];
    }else{
        int mid = (st+dr)/2;
        if(a <= mid && b >= mid+1){
            return query(2*nod, st, mid, a, b)+query(2*nod+1, mid+1, dr, a, b);
        }else if(a <= mid){
            return query(2*nod, st, mid, a, b);
        }else if(b >= mid+1){
            return query(2*nod+1, mid+1, dr, a, b);
        }
    }
}

int main()
{
    fin >> n >> m;
    build(1, 1, n);
    while(m--){
        fin >> x >> y;
        fout << query(1, 1, n, x, y).ssm << "\n";
    }
    return 0;
}