#include <cstdio>

#define file_in "sequencequery.in"
#define file_out "sequencequery.out"

#define nmax 600100

int n,q;
int a[nmax];
int b[nmax];
int c[nmax];
int sum[nmax];
int suma,sol;

inline int max(int a, int b) { return a>b?a:b; }

void update(int nod, int ls, int ld, int poz, int val)
{
	if (ls==ld)
	{
		a[nod]=val;
		b[nod]=val;
		c[nod]=val;
		sum[nod]=val;
		return ;
	}
	
	int mij=(ls+ld)>>1;
	
	if (poz<=mij)
		update(2*nod,ls,mij,poz,val);
	else
		update(2*nod+1,mij+1,ld,poz,val);
	a[nod]=max(a[2*nod],sum[2*nod]+a[2*nod+1]);
	b[nod]=max(b[2*nod+1],sum[2*nod+1]+b[2*nod]);
	c[nod]=max(max(c[2*nod],c[2*nod+1]),a[2*nod+1]+b[2*nod]);
	sum[nod]=sum[2*nod]+sum[2*nod+1];
	
	
}



void citire()
{
	
	int x;
	freopen(file_in,"r",stdin);
	freopen(file_out,"w",stdout);
	
	scanf("%d %d", &n, &q);
	for (int i=1;i<=n;++i)
	{
		scanf("%d", &x);
		update(1,1,n,i,x);
	}
}

void query(int nod, int ls, int ld, int left, int right)
{
	if (left<=ls && ld<=right)
	{
		sol=max(sol,suma+a[nod]);
		suma=max(suma+sum[nod],b[nod]);
		sol=max(sol,suma);
		sol=max(sol,c[nod]);
		return ;
	}
	
	int mij=(ls+ld)>>1;
	
	if (left<=mij)
		query(2*nod,ls,mij,left,right);
	if (mij<right)
		query(2*nod+1,mij+1,ld,left,right);
}

void solve()
{
	int a,b;
	while(q--)
	{
		scanf("%d %d", &a, &b);
		suma=sol=-0x3f3f3f3f;
		query(1,1,n,a,b);
		printf("%d\n", sol);
	}
}


int main()
{
	citire();
	solve();
	
	fclose(stdin);
	fclose(stdout);
	
	return 0;
	
}