#include <iostream>
#include <fstream>
#define ll long long
using namespace std;

ifstream f("sequencequery.in");
ofstream g("sequencequery.out");

struct structura{
    long long pref, post, suma, suma_maxima;
};

structura arbore[400005];

long long n, nr_q, x, st, dr, rez, alt_nr, post_q;

void update(int st, int dr, int poz_arbore, long long val, int ind_adaugat)
{
    if (st==dr) {
        arbore[poz_arbore] = {val, val, val, val};
        return;
    }
    int mij=(st+dr)/2;
    (mij>=ind_adaugat)?update(st,mij,poz_arbore*2,val,ind_adaugat):update(mij+1,dr,poz_arbore*2+1,val,ind_adaugat);
    arbore[poz_arbore].suma=arbore[poz_arbore*2].suma+arbore[poz_arbore*2+1].suma;
    arbore[poz_arbore].pref=max(arbore[poz_arbore*2].pref,arbore[poz_arbore*2].suma+arbore[poz_arbore*2+1].pref);
    arbore[poz_arbore].post=max(arbore[poz_arbore*2+1].post,arbore[poz_arbore*2].post+arbore[poz_arbore*2+1].suma);
    arbore[poz_arbore].suma_maxima=max(max(arbore[poz_arbore*2].suma_maxima,arbore[poz_arbore*2+1].suma_maxima),arbore[poz_arbore*2].post+arbore[poz_arbore*2+1].pref);
}

structura query(int st, int dr, int st_query ,int dr_query, int ind_arbore)
{
    if (st>=st_query && dr<=dr_query)
    {
        return arbore[ind_arbore];
    }
    if (st>dr_query || dr<st_query)
        return {-0x3f3f3f3f,-0x3f3f3f3f,-0x3f3f3f3f,-0x3f3f3f3f};
    int mij=(st+dr)/2;
    structura stanga=query(st,mij,st_query,dr_query,ind_arbore*2);
    structura dreapta=query(mij+1,dr, st_query, dr_query, ind_arbore*2+1);
    structura arb;
    arb.suma=stanga.suma+dreapta.suma;
    arb.pref=max(stanga.pref,stanga.suma+dreapta.pref);
    arb.post=max(dreapta.post,stanga.post+dreapta.suma);
    arb.suma_maxima=max(max(stanga.suma_maxima,dreapta.suma_maxima),stanga.post+dreapta.pref);
    return arb;
}

int main() {
    f >> n >> nr_q;
    for (int i=1; i<=n; ++i)
    {
        f >> x;
        update(1,n,1,x,i);
    }
    for (int q=1; q<=nr_q; ++q)
    {
        f >> st >> dr;
        rez=-0x3f3f3f3f;
        alt_nr=1;
        g <<query(1,n,st,dr,1).suma_maxima << '\n';

    }
    return 0;
}