#include <fstream>

using namespace std;

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

const int inf= 1<<30;
const int nmax= 100000;
const int pmax= 262144;

struct str {
    int b, e, a, s;
};

int sol, aux;
int v[nmax+1];
str arb[pmax+1];

void make_arb( int x, int l, int r ) {
    if ( l==r ) {
        arb[x].b= arb[x].e= arb[x].a= arb[x].s= v[r];
    } else {
        make_arb(x*2, l, (l+r)/2);
        make_arb(x*2+1, (l+r)/2+1, r);

        arb[x].b= max(arb[x*2].b, arb[x*2].s+arb[x*2+1].b);
        arb[x].e= max(arb[x*2+1].e, arb[x*2+1].s+arb[x*2].e);
        arb[x].a= max(arb[x*2+1].b+arb[x*2].e, max(arb[x*2].a, arb[x*2+1].a));
        arb[x].s= arb[x*2].s+arb[x*2+1].s;
    }
}

void query( int x, int l, int r, int a, int b) {
    if ( a<=l && r<=b ) {
        sol= max(max(arb[x].a, arb[x].b+aux), sol);
        aux= max(arb[x].e, aux+arb[x].s);
    } else if ( max(a, l)<=min(b, r) ) {
        query(x*2, l, (l+r)/2, a, b);
        query(x*2+1, (l+r)/2+1, r, a, b);
    }
}

int main(  ) {
    int n, m;
    fin>>n>>m;
    for ( int i= 1; i<=n; ++i ) {
        fin>>v[i];
    }
    make_arb(1, 1, n);

    for ( int cnt= 1; cnt<=m; ++cnt ) {
        int a, b;
        fin>>a>>b;

        sol= aux= -inf;
        query(1, 1, n, a, b);
        fout<<sol<<"\n";
    }

    return 0;
}