#include <fstream>
//#include <iostream>
using namespace std;

ifstream f("sequencequery.in");
ofstream g("sequencequery.out");
#define cout g

#define LE 160666
#define ll long long

ll Arb_sc[4*LE],Arb_dr[4*LE];
ll Arb_st[4*LE],Arb_sum[4*LE];
ll l[LE*4],A[LE*4];
int k,X,Y,n,m,i,U[LE*4];


void build(int st,int dr,int nod)
{
	int mij=(st+dr)/2;
	ll val=0;
	if (nod==8)
		int okz=true;
	
	if (st==dr)
	{
		 val=A[st];
		Arb_sc[nod]=val;
		Arb_st[nod]=val;
		Arb_dr[nod]=val;
		Arb_sum[nod]=A[st];
   //cout<<nod<<" "<<st<<" "<<dr<<"------"<<"stanga "<<Arb_st[nod]<<" dreapta "<<Arb_dr[nod]<<" SCMAX "<<Arb_sc[nod]<<'\n';	
		return;
	}
	
	build (st,mij,nod*2);
	build (mij+1,dr,nod*2+1);
	
	Arb_sc[nod]=max(Arb_sc[nod*2],Arb_sc[nod*2+1]);
	Arb_sc[nod]=max(Arb_dr[nod*2]+Arb_st[nod*2+1],Arb_sc[nod]);
	
	Arb_st[nod]=max(Arb_st[nod*2],    Arb_sum[nod*2]+Arb_st[nod*2+1]);
	Arb_dr[nod]=max(Arb_dr[nod*2+1],  Arb_sum[nod*2+1]+Arb_dr[nod*2]);
	Arb_sum[nod]=Arb_sum[nod*2]+Arb_sum[nod*2+1];
//	 cout<<nod<<" "<<st<<" "<<dr<<"------"<<"stanga "<<Arb_st[nod]<<" dreapta "<<Arb_dr[nod]<<" SCMAX "<<Arb_sc[nod]<<'\n';
}

void query_arb(int st,int dr,int nod)
{
	if (st>=X&&dr<=Y)
	{
		U[++k]=nod;
		return;
	}
	
	int mij=(st+dr)/2;
	if (mij>=X) query_arb(st,mij,nod*2);
	if (mij+1<=Y) query_arb(mij+1,dr,nod*2+1);
}

int query(int st,int dr)
{
	k=0,X=st,Y=dr;
	query_arb(1,n,1);
	ll result=-100000000,vmax=0;
	//for(int i=1;i<=k;++i) cout<<U[i]<<" ";
	
	for(int i=1;i<=k;++i) 
	{
		int nod=U[i];
		l[i]=max(Arb_dr[nod],Arb_sum[nod]+l[i-1]);
		l[i]=max((ll)0,l[i]);
		vmax=max(l[i-1]+Arb_st[nod],Arb_sc[nod]);
	    result=max(result,vmax);
	}
	return result;
}

int main()
{
	f>>n>>m;
	for(i=1;i<=n;++i)  f>>A[i];
	
	//for(i=1;i<=n;++i) cout<<A[i]<<" ";
	//cout<<'\n'<<'\n';
	
	build(1,n,1);
	//cout<<'\n'<<'\n';
	
	
	for(i=1;i<=m;++i)
	{
		int xx,yy;
		f>>xx>>yy;
		cout<<query(xx,yy)<<'\n';
	}
	
	return 0;
}