#include <iostream>
#include <fstream>

using namespace std;
ifstream fin("sequencequery.in");
ofstream fout("sequencequery.out");

int n,m,i,j,nr,a,b,p;
int ssm[200005],mx[200005],mn[200005],sum[100005];

void calc(int nd,int c1,int c2)
{
	ssm[nd]=max(mx[c2]-mn[c1], max(ssm[c1],ssm[c2]));
	mn[nd]=min(mn[c1],mn[c2]);
	mx[nd]=max(mx[c1],mx[c2]);
}

void create(int nd,int st,int dr)
{
	if(st==dr)
	{
		nr++;
		mn[nd]=sum[nr-1];
		mx[nd]=sum[nr];
		ssm[nd]=mx[nd]-mn[nd];
		return;
	}
	int md=(st+dr)/2;
	create(2*nd,st,md);
	create(2*nd+1,md+1,dr);
	
	calc(nd,2*nd,2*nd+1);
}

void query(int nd,int st,int dr)
{
	if(a<=st&&dr<=b)
	{
		if(p==0)
		{
			p=1;
			ssm[0]=ssm[nd];
			mn[0]=mn[nd];
			mx[0]=mx[nd];
			return;
		}
		calc(0,0,nd);
		return;
	}
	if(st>=dr)	return;
	int md=(st+dr)/2;
	if(max(st,a)<=min(md,b))	query(2*nd,st,md);
	if(max(md+1,a)<=min(dr,b))	query(2*nd+1,md+1,dr);
}

int main() {
	
	fin>>n>>m;
	for(i=1;i<=n;i++)
	{
		fin>>sum[i];
		sum[i]+=sum[i-1];
	}
	create(1,1,n);
	
	while(m--)
	{
		p=0;
		fin>>a>>b;
		query(1,1,n);
		fout<<ssm[0]<<"\n";
	}
}