#include <fstream>
using namespace std;
ifstream fin("sequencequery.in");
ofstream fout("sequencequery.out");
int i, n, m, x, a, b; long long INF = 2000000000;
struct sQuery{
    long long S, st, dr, Ssecv;
} v[4 * 100010], sol_global;
long long maxim(long long a, long long b)
{
    if( a > b)
        return a;
    return b;
}
void update(int nod, int st, int dr, int poz, int x){
    if(st == dr){
        v[nod].S = x; v[nod].st = x; v[nod].dr = x; v[nod].Ssecv = x;
        return;
    }
    int mid = (st + dr) / 2;
    if(poz <= mid)
        update(2 * nod, st, mid, poz, x);
    else
        update(2 * nod + 1, mid + 1, dr, poz, x);
    v[nod].st = maxim( v[2 * nod].st, v[2*nod].S + v[2 * nod + 1].st );
    v[nod].dr = maxim( v[2 * nod + 1].dr ,v[2 * nod  + 1].S + v[2 * nod].dr );
    v[nod].Ssecv=maxim( v[2 * nod].Ssecv, maxim(v[2 * nod + 1].Ssecv, v[2 * nod].dr + v[2 * nod + 1].st ) );
    long long sum = 0;
    if(v[2 * nod].S != -INF && v[2 * nod + 1].S != -INF)
        sum = v[2 * nod].S + v[2 * nod + 1].S;
    else
        sum = v[2 * nod].S + v[2 * nod + 1].S + INF;
        v[nod].S = sum;
}
sQuery query(int nod, int p, int u, int a, int b)
{
    sQuery s_st; sQuery s_dr;
    sQuery sol;
    if(a <= p && u <= b)
    {
        return v[nod];
    }
    int m = ( p + u) / 2;
    int ok_st = 0,  ok_dr = 0;
    if(a <= m){
        s_st = query(2 * nod, p, m , a, b);
        ok_st = 1;
    }
    if(m < b){
        s_dr = query(2 * nod + 1, m + 1, u, a, b);
        ok_dr = 1;
    }
    if(ok_st && ok_dr){
        sol.S = s_st.S + s_dr.S;
        sol.st = max(s_st.st, s_st.S + s_dr.st);
        sol.dr = max(s_dr.dr, s_dr.S + s_st.dr);
        sol.Ssecv = max(s_st.Ssecv, max(s_dr.Ssecv, s_st.dr + s_dr.st));
        return sol;
    }
    else
        if(ok_st)
            return s_st;
        else
            return s_dr;
}
int main()
{
    fin >> n >> m;
    for(i = 1; i <= 4 * n; i ++)
    {
     v[i].S = v[i].st = v[i].dr = v[i].Ssecv = -INF;
    }
    for(i = 1; i <= n; i ++)
    {
        fin >> x;
        update(1, 1, n, i, x);
    }
    for(i = 1; i <= m; i ++)
    {
        fin >> a >> b;
        sol_global = query(1,1,n,a,b);
        fout << sol_global.Ssecv << '\n';
    }
    return 0;
}