#include <fstream>
#define DIM 100002
#define INF 2e9

using namespace std;

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

int n, m, v[DIM], sst, sdr, smax, x, y;

struct arbint{
    int st, dr, smax, stlg, drlg, lgmax;
}aint[4 * DIM];

void build(int nod, int st, int dr){
    if(st == dr){
        aint[nod].st = v[st];
        aint[nod].dr = v[st];
        aint[nod].smax = v[st];
        aint[nod].stlg = 1;
        aint[nod].drlg = 1;
        aint[nod].lgmax = 1;
        return;
    }

    int mid = (st + dr) / 2;

    build(nod<<1, st, mid);
    build(nod<<1|1, mid + 1, dr);

    aint[nod].smax = max(aint[nod<<1].smax, max(aint[nod<<1|1].smax, aint[nod<<1].dr + aint[nod<<1|1].st));

    if(aint[nod].smax == aint[nod<<1].dr + aint[nod<<1|1].st){
        aint[nod].lgmax = aint[nod<<1].drlg + aint[nod<<1|1].stlg;
    }
    else{
        if(aint[nod].smax == aint[nod<<1].smax)
            aint[nod].lgmax = aint[nod<<1].lgmax;
        else
            aint[nod].lgmax = aint[nod<<1|1].lgmax;
    }

    if(aint[nod<<1].stlg == mid - st + 1 && aint[nod<<1|1].st > 0){
        aint[nod].st = aint[nod<<1].st + aint[nod<<1|1].st;
        aint[nod].stlg = aint[nod<<1].stlg + aint[nod<<1|1].stlg;
    }
    else{
        aint[nod].st = aint[nod<<1].st;
        aint[nod].stlg = aint[nod<<1].stlg;
    }

    if(aint[nod<<1|1].drlg == dr - mid && aint[nod<<1].dr > 0){
        aint[nod].dr = aint[nod<<1].dr + aint[nod<<1|1].dr;
        aint[nod].drlg = aint[nod<<1].drlg + aint[nod<<1|1].drlg;
    }
    else{
        aint[nod].dr = aint[nod<<1|1].dr;
        aint[nod].drlg = aint[nod<<1|1].drlg;
    }
}

void query(int nod, int st, int dr, int a, int b){
    if(a <= st && b >= dr){
        sst = sdr + aint[nod].st;
        if(aint[nod].lgmax == dr - st + 1)
            sdr = sdr + aint[nod].dr;
        else
            sdr = aint[nod].dr;
        smax = max(max(smax, aint[nod].smax), max(sst, sdr));
        return;
    }

    int mid = (st + dr) / 2;

    if(a <= mid)
        query(nod<<1, st, mid, a, b);
    if(b > mid)
        query(nod<<1|1, mid + 1, dr, a, b);
}

int main()
{
    in>>n>>m;
    for(int i = 1; i <= n; ++ i)
        in>>v[i];
    build(1, 1, n);
    for(int i = 1; i <= m; ++ i){
        in>>x>>y;
        sst = 0;
        sdr = 0;
        smax = -INF;
        query(1, 1, n, x, y);
        out<<smax<<'\n';
    }
    return 0;
}