#include <fstream>
using namespace std;
ifstream fin("sequencequery.in");
ofstream fout("sequencequery.out");

#define maxn 100005
#define oo 200000000
#define ll long long

int i,N,M,a,b;
int v[maxn],A[4*maxn],S[4*maxn],L[4*maxn],R[4*maxn];
ll r,s;

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

void citire()
{
	fin >> N >> M;
	for(i=1;i<=N;i++)
		fin >> v[i];
}

void init(int k, int st, int dr)
{
	if(st==dr)
	{
		A[k]=L[k]=R[k]=S[k]=v[st];
		return;
	}
	
	int m=st+(dr-st)/2;
	init(2*k,st,m);
	init(2*k+1,m+1,dr);
	
	L[k]=max(L[2*k],S[2*k]+L[2*k+1]);
	R[k]=max(R[2*k+1],R[2*k]+S[2*k+1]);
	A[k]=max(max(A[2*k],A[2*k+1]),R[2*k]+L[2*k+1]);
	S[k]=S[2*k]+S[2*k+1];
}

void query(int k, int st, int dr)
{
	if(a<=st && dr<=b)
	{
		r=max(r,max(s+L[k],A[k]));
		s=max(s+S[k],R[k]);
		return;
	}
	int m=st+(dr-st)/2;
	if(a<=m) query(2*k,st,m);
	if(m<b) query(2*k+1,m+1,dr);
}

int main()
{
	citire();
	init(1,1,N);
	for(;M;M--)
	{
		fin >> a >> b;
		r=s=-oo;
		query(1,1,N);
		fout << r << '\n';
	}
}