#include <stdio.h>
#include <fstream>

using namespace std;

typedef struct nod{
	long long x, y; 
	double min, max, sum;
} nod;
	
double s[200001];
nod T[300002];

double maxSeq(long long p, long long q)
{
	long long i;
	double smax, min;
	
	smax = -10000000001.0;
	min = s[p-1];
	for (i = p; i <= q; i++)
	{
		if (s[i] < min) min = s[i];
		if (s[i] - min > smax) smax = s[i] - min;
	}
	
	return smax;
}

void buildArb(long long n, long long p, long long q)
{
	if (p == q)
	{
		T[n].min = s[p-1];
		T[n].max = s[p];
		T[n].sum = s[p] - s[p-1];
		T[n].x = T[n].y = p;
	}
	else {
		buildArb(2*n, p, (p+q)/2);
		buildArb(2*n+1, 1 + (p+q)/2, q);
		T[n] = T[2*n+1];
		if (T[n].min > T[2*n].min) T[n].min = T[2*n].min;
		if (T[n].max < T[2*n].max) T[n].max = T[2*n].max;
		T[n].x = p;
		T[n].y = q;
		T[n].sum = maxSeq(p, q);
	}
	
	return;
}

nod query(long long p, long long q, long long l, long long r, long long n)
{
	nod x1, x2, x;
	
	if (p <= l && r <= q) return T[n];
	else {
		if (p <= (l+r)/2) x1 = query(p, q, l, (l+r)/2, 2*n);
		if (q > (l+r)/2) x2 = query(p, q, 1 + (l+r)/2, r, 2*n+1);
		
		if (q <= (l+r)/2) return x1;
		if (p > (l+r)/2) return x2;
		
		x = x1;
		if (x.sum < x2.sum) x.sum = x2.sum;
		if (x.sum < x2.max - x1.min) x.sum = x2.max - x1.min;
		if (x.min > x2.min) x.min = x2.min;
		if (x.max < x2.max) x.max = x2.max;
	}
	
	return x;
}

int main()
{
	fstream f, g;
	long long n, i, m, p , q;
	nod x;
	double t;
	
	f.open("sequencequery.in", ios :: in);
	g.open("sequencequery.out", ios :: out);
	
	f >> n >> m;
	for (i = 0; i < n; i++)
	{
		f >> t;
		s[i+1] = s[i] + t;
	}
	
	buildArb(1, 1, n);
	
	for (i = 0; i < m; i++)
	{
		f >> p >> q;
		x = query(p, q, 1, n, 1);
		g << x.sum << endl;
	}
	
	g.close();
	f.close();
	
	return 0;
}