//explicatie la MaxQ

#include<fstream>
#define MaxN 300005
#define left (2*n)
#define right (2*n+1)
#define mid ((st+dr)/2)
#define INF 1<<30

using namespace std;

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

int v[MaxN],i,j,m,n,a,b;
long long A[MaxN], B[MaxN], C[MaxN], sum[MaxN],Sum, bestSum;

void build(int n, int st, int dr)
{	if(st==dr)
		A[n]=B[n]=C[n]=sum[n]=v[st];
	else
	{	build(left, st, mid);
		build(right, mid+1, dr);
		A[n]=max(A[left],sum[left]+A[right]);
		B[n]=max(B[left]+sum[right],B[right]);
		C[n]=max(max(C[left],C[right]),B[left]+A[right]);
		sum[n]=sum[left]+sum[right];
	}
}

void query(int n, int st, int dr)
{	if(a<=st&&dr<=b)
	{	bestSum=max(bestSum,max(Sum+A[n],C[n]));
		Sum=max(Sum+sum[n],B[n]);
	}
	else
	{	if(a<=mid)	query(left, st, mid);
		if(b>mid)	query(right, mid+1, dr);
	}
}

int main()
{	fin>>n>>m;
	for(i=1;i<=n;i++) fin>>v[i];
	build(1,1,n);
	for(i=1;i<=m;i++)
	{	fin>>a>>b;
		bestSum=Sum=-INF;
		query(1,1,n);
		fout<<bestSum<<'\n';
	}
	return 0;
}