#include <cstdio>
#include <algorithm>
#define infile "sequencequery.in"
#define outfile "sequencequery.out"
#define n_max 100005
#define INF -(1<<30)
#define set(x, val) x.l = x.r = x.sum = x.tsum = val;
using namespace std;

int N, M;

struct NOD
{
   int l, r, sum, tsum;
}  AI[3*n_max] = {0, 0, 0, 0};



void update (int nod, int st, int dr, int a, int b, int val)
{
	if(a<=st && dr<=b)
	{
		set(AI[nod], val);
		return;
	}
	
	int mij = st + (dr - st)/2;
	
	if(a <= mij)
		update(2*nod, st, mij, a, b, val);
	if(mij < b)
		update(2*nod+1, mij+1, dr, a, b, val);
	
	AI[nod].tsum = AI[2*nod].tsum + AI[2*nod+1].tsum;
	
	AI[nod].l = max(AI[2*nod].l, AI[2*nod].tsum +  AI[2*nod+1].l);
	AI[nod].r = max(AI[2*nod+1].r, AI[2*nod+1].tsum +  AI[2*nod].r);
	
	AI[nod].sum = max(AI[2*nod].sum, AI[2*nod+1].sum);
	AI[nod].sum = max( max(AI[nod].sum, AI[2*nod].r + AI[2*nod+1].l) , max(AI[nod].l, AI[nod].r)); 
}


NOD query(int nod, int st, int dr, int a, int b)
{
	NOD rez;
	set(rez,INF);
	
	if(a<=st && dr<=b)
	{
		rez = AI[nod];
		return rez;
	}
	
	NOD N1, N2;
	set(N1,INF);
	set(N2,INF);
	
	int mij = st + (dr - st)/2;
	
	if(a<=mij)
		N1 = query(2*nod, st, mij, a, b);
	if(mij<b)
		N2 = query(2*nod+1, mij+1, dr, a, b);
	
	rez.tsum = (N1.tsum!=INF) ? N1.tsum : 0;
	rez.tsum += (N2.tsum!=INF) ? N2.tsum : 0;
	
	if(N1.l != INF)
	{
		rez.l = N1.l;
		if(N2.l != INF)
			rez.l = max(rez.l, N1.tsum + N2.l);
	}
	
	if(N2.r != INF)
	{
		rez.r = N2.r;
		if(N1.r != INF)
			rez.r = max(rez.r, N2.tsum + N1.r);
	}
	
	rez.sum = max(N1.sum, N2.sum);
	rez.sum = max(rez.sum, max(rez.l, rez.r));
	rez.sum = max(rez.sum, N1.r + N2.l);
	
	return rez;
}


int main(void)
{
    freopen(infile, "r", stdin);
	freopen(outfile, "w", stdout);
    
	int x, y;
	
	scanf("%d %d", &N, &M);
	
	for(int i=1; i<=N; ++i)
	{
		scanf("%d",&x);
		update(1,1,N,i,i,x);
	}
	
	while(M--)
	{
		scanf("%d %d",&x, &y);
			
		NOD rez = query(1, 1, N, x, y);
		
	    printf("%d\n", rez.sum);  
	}

    fclose(stdin);
	fclose(stdout);
    
    return 0;
}