using namespace std;
#include <cstdio>
#include <algorithm>
#define maxn 100001
#define left(i) ( (i)<<1 )
#define right(i) (((i)<<1)|1)
long long lf[maxn*3], rt[maxn*3], sol[maxn*3], sum[maxn*3];
long long a[maxn];
int n, m;

void read()
{
	freopen("sequencequery.in","r",stdin);
	scanf("%d %d\n", &n, &m);
	for(int i=1;i<=n;++i) scanf("%lld ", a+i);
}

void build(int n, int l, int r) 
{
	if(l==r)
	{
		lf[n]=rt[n]=sol[n]=a[l]>?0;
		sum[n]=(long long)a[l];
		return;
	}
	int m=(l+r)>>1;
	build(left(n), l, m);
	build(right(n), m+1, r);
	
	lf[n]=max(lf[left(n)], sum[left(n)]+lf[right(n)]);
	rt[n]=max(rt[left(n)]+sum[right(n)], rt[right(n)]);
	sol[n]=max(max(sol[left(n)], sol[right(n)]), rt[left(n)]+lf[right(n)]);
	/*
	
	lf[n]=lf[left(n)]>?(sum[left(n)]+lf[right(n)]);
	rt[n]=rt[right(n)]>?(sum[right(n)]+rt[left(n)]);
	sol[n]=sol[left(n)]>?sol[right(n)];
	sol[n]>?=rt[left(n)]+lf[right(n)];
	*/
	sum[n]=sum[left(n)]+sum[right(n)];
}
int x, y;
long long S, ans;
void query(int n, int l, int r)//x, y
{
	if(x<=l && r<=y)
	{
		if(S<0)S=0;
		
		ans=max(ans, max(S+lf[n], sol[n]));
		S=max(S+sum[n], rt[n]);
		//ans=S+lf[n];
		
		//ans=max(ans, sol[n]);
		//ans>?=sol[n];
		//S=S+sum[n];
		//S=max(S, rt[n]);
		//S>?=rt[n];
		return;
	}

	int m=(l+r)>>1;
	if(x<=m) query(left(n), l, m);
	if(y>m) query(right(n), m+1,r);
}
	
	


int main()
{
	freopen("sequencequery.out", "w",stdout);
	read();
	build(1, 1, n);
	while(m--)
	{
		scanf("%d %d\n", &x, &y);
		S=ans=0;
		
		query(1, 1, n);
		printf("%lld\n", ans);
	}
	
	
	return 0;
}