#include <stdio.h>
FILE *f=fopen ("sequencequery.in", "r");
FILE *g=fopen ("sequencequery.out", "w");
const int r=600001;
struct arbore { long long S,D,C,sum;	}	v[r];
long long sol,s;
int n,m,i,val,x,y;

long long maxim(int a, int b)
{
	return (a>b) ? a : b;
}

void valori(int p, int s, int d) 
{
	v[p].sum=v[s].sum+v[d].sum;
	v[p].S=maxim(v[s].S, v[s].sum+v[d].S);
	v[p].D=maxim(v[d].D, v[d].sum+v[s].D);
	v[p].C=maxim( maxim(v[s].C, v[d].C), maxim(v[s].D+v[d].S, v[p].sum) );
}
	
void update(int poz, int ls, int ld) {
int h;
	if (ls==ld)
	{
		v[poz].S=v[poz].D=v[poz].C=v[poz].sum=val;
		return;
	}
	
	h=(ls+ld)/2;
	if (i<=h)	update(2*poz, ls, h);
	else		update(2*poz+1, h+1, ld);
	
	valori(poz, 2*poz, 2*poz+1);
}

void query(int poz, int ls, int ld) {
int h;
	if (x<=ls && ld <= y)
	{
		sol=maxim(sol, maxim(s+v[poz].S, v[poz].C) );
		s=maxim (s+v[poz].sum, v[poz].D);
		return;
	}
	
	h=(ls+ld)/2;
	if (x<=h)	query(2*poz, ls, h);
	if (y>h)	query(2*poz+1, h+1, ld);
}

void initializare() {
int i;	sol=1;
for (i=1;i<=15;i++)
	sol*=i;
sol*=-1;
}

int main() {
fscanf (f, "%d%d", &n,&m);

for (i=1;i<=n;i++)
{
	fscanf (f, "%d", &val);
	update(1,1,n);
}

for (i=1;i<=m;i++)
{
	fscanf (f, "%d%d", &x, &y);		s=0;	initializare();
	query(1,1,n);
	
	fprintf (g, "%lld\n", sol);
}

return 0;
}