#include<iostream>
#include<fstream>
#include<algorithm>
using namespace std;
struct interval {
	int poz,st,dr;
};
long long s[400001],l[400001],r[400001];
int v[100001],n,bestsum,a,b,nr;
interval d[100001];
long long ssm(int p, int q)
{
	int i;
	long long max,s;
	s=0;
	max=-2000000000;
	for(i=p;i<=q;i++) {
		if(s<0)
			s=v[i];
		else s=s+v[i];
		if(s>max)
			max=s;
	}
	return max;
}
int maxim(int a, int b)
{
	if(a>=b)
		return a;
	return b;
}
void update(int nod, int st, int dr)
{
	int mij,i;
	long long smax,sum;
	if(st==dr) {
		s[nod]=v[st];
		l[nod]=v[st];
		r[nod]=v[st];
		return;
	}
	mij=(st+dr)/2;
	update(nod*2,st,mij);
	update(nod*2+1,mij+1,dr);
	smax=-2000000000;
	sum=0;
	for(i=dr;i>=st;i--) {
		sum=sum+v[i];
		if(sum>smax)
			smax=sum;
	}
	r[nod]=smax;
	smax=-2000000000;
	sum=0;
	for(i=st;i<=dr;i++) {
		sum=sum+v[i];
		if(sum>smax)
			smax=sum;
	}
	l[nod]=smax;
	s[nod]=maxim((r[nod*2]+l[nod*2+1]),ssm(st,dr));
}
void query(int nod, int st, int dr)
{
	int mij;
	if((a<=st)&&(dr<=b)) {
		nr++;
		d[nr].poz=nod;
		d[nr].st=st;
		d[nr].dr=dr;
		return;
	}
	mij=(st+dr)/2;
	if(a<=mij)
		query(2*nod,st,mij);
	if(mij<b)
		query(2*nod+1,mij+1,dr);
}
inline bool cmp(const interval a, const interval b)
{
	return a.st<b.st;
}
void rezolva()
{
	int i;
	long long st,dr;
	sort(d+1,d+nr+1,cmp);
	st=l[d[1].poz];
	dr=r[d[1].poz];
	bestsum=s[d[1].poz];
	for(i=2;i<=nr;i++) {
		if(s[d[i].poz]>bestsum)
			bestsum=s[d[i].poz];
		if((dr+l[d[i].poz])>bestsum)
			bestsum=dr+l[d[i].poz];
		if((r[d[i].poz]+dr)>dr)
			dr=r[d[i].poz]+dr;
	}
}
int main ()
{
	int i,m;
	ifstream f("sequencequery.in");
	ofstream g("sequencequery.out");
	f>>n>>m;
	for(i=1;i<=n;i++)
		f>>v[i];
	update(1,1,n);
	for(i=1;i<=m;i++) {
		f>>a>>b;
		bestsum=-2000000000;
		nr=0;
		query(1,1,n);
		rezolva();
		g<<bestsum<<'\n';
	}
	f.close();
	g.close();
	return 0;
}