#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, stot;
}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].stot = v[st];
        return;
    }

    int mid = (st + dr) / 2;

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

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

void query(int nod, int st, int dr, int a, int b){
    if(a <= st && b >= dr){
        if(aint[nod].stot == aint[nod].dr)
            sdr = max(sdr + aint[nod].dr, aint[nod].dr);
        else
            sdr = aint[nod].dr;
        smax = max(sdr, max(smax, aint[nod].smax));
        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;
}