#include <iostream>

using namespace std;

#define LL long long
#define maxN 100010
#define inf (1LL << 60)


LL sol, var, Sum[maxN * 3], Best[maxN * 3], Left[maxN * 3], Right[maxN * 3];


void update (int nod, int left, int right, LL val, int pos)
{
	if (left == right)
	{
		Sum[nod] = val;
		Best[nod] = val;
		Left[nod] = val;
		Right[nod] = val;
		
		return;
	}
	
	int mid = (left + right) / 2;
	
	if (pos <= mid) update (nod * 2, left, mid, val, pos);
	else update (nod * 2 + 1, mid + 1, right, val, pos);
	
	Sum[nod] = Sum[nod * 2] + Sum[nod * 2 + 1];
	Left[nod] = max (Left[nod * 2], Sum[nod * 2] + Left[nod * 2 + 1]);
	Right[nod] = max (Right[nod * 2 + 1], Sum[nod * 2 + 1] + Right[nod * 2]);
	Best[nod] = max (Best[nod * 2], Best[nod * 2 + 1]);
	Best[nod] = max (Best[nod], Right[nod * 2] + Left[nod * 2 + 1]);
}



void query (int nod, int left, int right, int a, int b)
{
	if (a <= left && b >= right)
	{
		if (var < 0) var = 0;
		
		LL aux = max (var + Left[nod], Best[nod]);
		
		sol = max (sol, aux);
		var = max (var + Sum[nod], Right[nod]);
		
		return;
	}
	
	int mid = (left + right) / 2;
	
	if (a <= mid) query (nod * 2, left, mid, a, b);
	if (b > mid) query (nod * 2 + 1, mid + 1, right, a, b);
}



int main()
{
	freopen ("sequencequery.in", "r", stdin);
	freopen ("sequencequery.out", "w", stdout);
	
	int N, M;
	
	scanf ("%d %d", &N, &M);
	
	for (int i = 1; i <= N; ++ i)
	{
		LL val;
		
		scanf ("%lld", &val);
		
		update (1, 1, N, val, i);
	}
	
	
	for (int i = 1; i <= M; ++ i)
	{
		int a, b;
		
		scanf ("%d %d", &a, &b);
		
		sol = - inf;
		var = 0;
		
		query (1, 1, N, a, b);
		
		printf ("%lld\n", sol);
	}
	
	return 0;
}