#include <stdio.h>
#include <iostream>
#define INF 999999999
using namespace std;
FILE *in,*out;

int n,m,lf,rg,sol,s;
int v[100002];

struct name {
    int tot,l,r,ans;
} ai[400002];

void read() {
    fscanf(in,"%d %d",&n,&m);
    for(int i=1; i<=n; i++)
        fscanf(in,"%d",&v[i]);
}

void update(int node, int left, int right) {
    if(left==right) {
        ai[node].l=ai[node].r=ai[node].ans=ai[node].tot=v[left];
        return;
    }
    int mij=(left+right)/2;
    update(node*2,left,mij);
    update(node*2+1,mij+1,right);

    ai[node].l=max(ai[node*2].l,ai[node*2].tot+ai[node*2+1].l);
    ai[node].r=max(ai[node*2+1].r,ai[node*2+1].tot+ai[node*2].r);
    ai[node].tot=ai[node*2].tot+ai[node*2+1].tot;
    ai[node].ans=max(ai[node*2].ans,max(ai[node*2+1].ans,ai[node*2+1].l+ai[node*2].r));
}

void querry(int node, int left, int right) {
    if(lf<=left && rg>=right) {
        if(s<0)
            s=0;
        sol=max(sol,max(s+ai[node].l,ai[node].ans));
        s=max(s+ai[node].tot, ai[node].r);
        return;
    }
    int mij=(left+right)/2;
    if(lf<=mij)
        querry(2*node, left, mij);
    if(rg>mij)
        querry(2*node+1, mij+1, right);

}

void solve() {
    update(1,1,n);
    for(int i=1; i<=m; i++) {
        fscanf(in,"%d %d",&lf,&rg);
        s=sol=-INF;
        querry(1,1,n);
        fprintf(out,"%d\n",sol);
    }
}

int main() {
    in=fopen("sequencequery.in","r");
    out=fopen("sequencequery.out","w");
    read();
    solve();
    return 0;
}