#include <cstdio>
#include <algorithm>
using namespace std;

const int N=100005;
struct nod{
    long long s,st,dr,best;
} v[4*N],aux;

int place[N],sem;

nod Union(nod a, nod b){
    nod c;
    c.s=a.s+b.s;
    c.st=max(a.st, a.s+b.dr);
    c.dr=max(b.dr, b.s+a.dr);
    c.best=max( max( max(a.best, b.best), max(c.st, c.dr) ), a.dr+b.st);
    return c;
}

void update(int pos, int st, int dr, int a, long long val){
    if(st>a) return;
    if(dr<a) return;

    if(st==dr){
        v[pos].s=val;
        v[pos].st=val;
        v[pos].dr=val;
        v[pos].best=val;
        return;
    }

    update(2*pos, st, (st+dr)/2, a, val);
    update(2*pos+1, (st+dr)/2+1, dr, a, val);

    v[pos]=Union(v[2*pos],v[2*pos+1]);
}

void query(int pos, int st, int dr, int a, int b){
    if(st>b) return;
    if(dr<a) return;

    if(a<=st and dr<=b){
        if(sem==0) sem=1, aux=v[pos];
        else aux=Union(aux, v[pos]);
        return;
    }

    query(2*pos, st, (st+dr)/2, a, b);
    query(2*pos+1, (st+dr)/2+1, dr, a, b);
}

int main(){
    freopen("sequencequery.in","r",stdin);
    freopen("sequencequery.out","w",stdout);

    int n,m,i,x,a,b;
    scanf("%d%d",&n,&m);
    for(i=1;i<=n;i++){
        scanf("%d",&x);
        update(1,1,n,i,1ll*x);
    }
    for(i=1;i<=m;i++){
        scanf("%d%d",&a,&b);
        sem=0;
        query(1,1,n,a,b);
        printf("%lld\n",aux.best);
    }

    return 0;
}