#include<stdio.h>
#include<stdlib.h>
#define MAXN 262145
#define INF 10000000005ll
#define Min(a, b)(a)<(b)?(a):(b)
#define Max(a, b)(a)>(b)?(a):(b)
long long min[MAXN],max[MAXN],sum[MAXN],secv[MAXN],x,a,b,S,minim,poz;
void sequence(int st, int dr, int nod){
    if(st==dr){
        max[nod]=sum[st];
        min[nod]=sum[st-1];
        secv[nod]=x;
    }
    else{
        int m=(st+dr)>>1;
        if(poz<=m)
			sequence(st,m,2*nod);
        else
			sequence(m+1,dr,2*nod+1);
        min[nod]=Min(min[2*nod],min[2*nod+1]);
        max[nod]=Max(max[2*nod],max[2*nod+1]);
        secv[nod]=Max(Max(secv[2*nod],secv[2*nod+1]),max[2*nod+1]-min[2*nod]);
    }
}
void query(int st, int dr, int nod){
    if(a<=st && dr<=b){
        S=Max(S,secv[nod]);
        if(minim!=INF)
            S=Max(S,max[nod]-minim);
        if(minim>min[nod])
			minim=min[nod];
    }
    else{
        int m=(st+dr)>>1;
        if(a<=m)
			query(st, m, 2*nod);
        if(b>m)
			query(m+1, dr, 2*nod+1);
    }
}
int main(){
    freopen("sequencequery.in","r",stdin);
    freopen("sequencequery.out","w",stdout);
    int i, n, m;
    scanf("%d %d",&n,&m);
    for(i=1;i<=n;i++){
        scanf("%lld",&x);
        poz=i;
        sum[i]=sum[i-1]+x;
        sequence(1, n, 1);
    }
	for(i=0;i<m;i++){
        scanf("%d %d", &a, &b);
        S=-INF;
		minim=INF;
        query(1,n,1);
        printf("%lld\n",S);
    }
	fclose(stdin);
	fclose(stdout);
    return 0;
}