#include <cstdio>
#include <cstdlib>
#include <algorithm>
using namespace std;


#define nmax 130010
#define oo ((1 << 62) - 1)
#define leftSon (node << 1)
#define rightSon ((node << 1) + 1)


struct data
{
	long long L, R, Sum, Best;
}Aint[4 * nmax];
int N, V[nmax], M, X, Y;
long long S, ans;


void BuildTree(int node, int left, int right)
{
	if(left == right)
	{
		Aint[node].L = Aint[node].R = Aint[node].Sum = Aint[node].Best = V[left];
		return ;
	}
	int mid = (left + right) / 2;
	BuildTree(leftSon, left, mid);
	BuildTree(rightSon, mid + 1, right);
	Aint[node].L = max(Aint[leftSon].L, Aint[leftSon].Sum + Aint[rightSon].L);
	Aint[node].R = max(Aint[rightSon].R, Aint[rightSon].Sum + Aint[leftSon].R);
	Aint[node].Best = max(max(Aint[leftSon].Best, Aint[rightSon].Best), Aint[leftSon].R + Aint[rightSon].L);
	Aint[node].Sum = Aint[leftSon].Sum + Aint[rightSon].Sum;
}

void Query(int node, int left, int right)
{
	if(X <= left && right <= Y)
	{
		if(S < 0) S = 0;
		ans = max(ans, max(Aint[node].Best, Aint[node].L + S));
		S = max(S + Aint[node].Sum, Aint[node].R);
		return ;
	}
	int mid = (left + right) / 2;
	if(X <= mid) Query(leftSon, left, mid);
	if(mid < Y) Query(rightSon, mid + 1, right);
}

int main()
{
	freopen("sequencequery.in", "r", stdin);
	freopen("sequencequery.out", "w", stdout);
	int i;
	scanf("%i %i", &N, &M);
	for(i = 1; i <= N; i++)
		scanf("%i", &V[i]);
	BuildTree(1, 1, N);
	for(; M; M --)
	{
		scanf("%i %i", &X, &Y);
		S = 0LL;
		ans = -100000000LL;
		Query(1, 1, N);
		printf("%lld\n", ans);
	}
	return 0;
}