#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);
}

void query(int st, int dr, int st_q, int dr_q, int ind_arbore)
{
    if (st>=st_q && dr<=dr_q)
    {
        if (alt_nr==1)
        {
            alt_nr++;
            post_q=arbore[ind_arbore].post;
            rez=arbore[ind_arbore].suma_maxima;
        }
        else
        {
            rez=max(rez,max(arbore[ind_arbore].suma_maxima,post_q+arbore[ind_arbore].pref));
        }
        return;
    }
    int mij=(st+dr)/2;
    if (mij>=dr_q)
    {
        query(st,mij,st_q,dr_q,ind_arbore*2);
    }
    else if (mij<st_q)
    {
        query(mij+1,dr,st_q,dr_q,ind_arbore*2+1);
    }
    else
    {
        query(st,mij,st_q,dr_q,ind_arbore*2);
        query(mij+1,dr,st_q,dr_q,ind_arbore*2+1);
    }
}

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;
        query(1,n,st,dr,1);
        g << rez << '\n';
    }
    return 0;
}