#include <iostream>
#include <cstdio>
#define BIG 1e9
using namespace std;

const int NMAX = 100001;
long long v[NMAX],x,y,ans,S;
struct tree{
    long long smax, st_max, dr_max, sum;
}arb[4 * NMAX];

void unite(tree &Res, tree f1, tree f2){
    Res.smax = max(max(f1.smax, f2.smax), f1.dr_max + f2.st_max);
    Res.st_max = max(f1.st_max, f1.sum + f2.st_max);
    Res.dr_max = max(f1.dr_max + f2.sum, f2.dr_max);
    Res.sum = f1.sum + f2.sum;
}

void build(int nod, int st, int dr){
    if(st == dr){
        arb[nod].smax = arb[nod].sum = arb[nod].st_max = arb[nod].dr_max = v[st];
        return;
    }
    int mij = (st+dr)/2;
    build(2*nod, st, mij);
    build(2*nod+1, mij+1, dr);
    unite(arb[nod], arb[2*nod], arb[2*nod + 1]);
}

void query(int nod, int st, int dr){
    if(x <= st && dr <= y){
        if(S < 0)
            S = 0;
        ans = max(ans, max(S + arb[nod].st_max, arb[nod].smax));
        S = max(S + arb[nod].sum, arb[nod].dr_max);
        return;
    }
    int mij = (st+dr)/2;
    if(x <= mij)
        query(2*nod, st, mij);
    if(mij + 1 <= y)
        query(2*nod + 1, mij + 1, dr);
}

int main()
{
    FILE *fin, *fout;
    int n,m,i;
    fin = fopen("sequencequery.in","r");
    fout = fopen("sequencequery.out","w");
    fscanf(fin,"%d %d",&n,&m);
    for(i=1;i<=n;i++)
        fscanf(fin,"%lld",&v[i]);
    build(1,1,n);
    for(i=0;i<m;i++){
        fscanf(fin,"%d %d",&x,&y);
        ans = S = -BIG;
        query(1,1,n);
        fprintf(fout,"%lld\n",ans);
    }
    fclose(fin);
    fclose(fout);
    return 0;
}