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

using namespace std;

typedef struct nod{
	long long min, max, sum;
} nod;
	
long long s[100001];
nod T[400010];


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];
	}
	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].sum = T[2*n].sum;
		if (T[n].sum < T[2*n + 1].sum) T[n].sum = T[2*n + 1].sum;
		if (T[n].sum < T[2*n +1].max -T[2*n].min) T[n].sum = T[2*n + 1].max - T[2*n].min;
	}
	
	return;
}

nod query(long long p, long long q, long long l, long long r, long long n)
{
	nod x1, x2, x;
	long long m = (l+r)/2;
	
	if (p <= l && r <= q) return T[n];
	else {
		if (p <= m) x1 = query(p, q, l, m, 2*n);
		if (q > m) x2 = query(p, q, 1 + m, r, 2*n+1);
		else return x1;
		
		//if (q <= m) return x1;
		if (p > m) 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;
	long long  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;
}