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


#define FIN "sequencequery.in"
#define FOUT "sequencequery.out"

#define MAX_N (1<<19)
#define max(a, b) ((a) > (b) ? (a) : (b))

int N, M;
int v[MAX_N];
long long A[MAX_N<<1], B[MAX_N<<1], C[MAX_N<<1], Sum[MAX_N<<1];

#define lf (n<<1)
#define rt (lf+1)
#define md ((l+r)>>1)

void build(int n, int l, int r)
{
	if (l == r) {
		A[n] = B[n] = C[n] = max(v[l], 0);
		Sum[n] = v[l];
	} else {
		build(lf, l, md);
		build(rt, md+1, r);

		A[n] = max(A[lf], Sum[lf]+A[rt]);
		B[n] = max(B[lf]+Sum[rt], B[rt]);
		C[n] = max(max(C[lf], C[rt]), B[lf]+A[rt]);
		
		Sum[n] = Sum[lf]+Sum[rt];
	}
}


int a, b;
long long ans, S;

void query(int n, int l, int r) 
{
	if (a <= l && r <= b) {
		if (S < 0) S = 0;
		ans = max(ans, max(S+A[n], C[n]));
		S = max(S+Sum[n], B[n]);
	} else {
		if (a <= md) query(lf,l, md);
		if (b >  md) query(rt, md+1,  r);
	}
}

int main()
{
	int i, t, v1, v2,j,p;
	
	freopen(FIN, "r", stdin);
	freopen(FOUT, "w", stdout);

	scanf("%d %d", &N,&M);
	for (i = 1; i <= N; ++i)
		scanf("%d", v+i);
	build(1, 1, N);
	for (i=1; i<=M; i++)
    {
        t=1;  
		scanf("%d %d",&v1, &v2);
        	S = ans = 0;
			a = v1;
			b = v2;
			query(1, 1, N);
            if (ans==0) 
             { 
               p=-1000000;         
               for (j=a; j<=b; j++) 
                {
                if (v[j]>p) p=v[j];
                if (p>0) break;
                }
              if (p<0) ans=p;        
              }
			printf("%lld\n", ans);
	}
	return 0;
}