#include <stdio.h>
#include <vector>
using namespace std;

typedef long long ll;
struct un_nod
{
	ll s_st, s_dr, s_max, s_tot;
};

int n, pos, val, seq_start, seq_end;
ll maxim, dreapta;
vector<un_nod> arb;

void solve();
void update(int, int, int);
void query(int, int, int);
inline ll max(ll, ll);
inline ll max(ll, ll, ll);
inline ll max(ll, ll, ll, ll);

int main()
{
	solve();
	unsigned int i;
	printf ("suma totala:\n");
	for (i = 1; i < arb.size(); ++i)
	{
		printf ("%lld ", arb[i].s_tot);
	}
	printf ("\n\nsuma stanga:\n");
	for (i = 1; i < arb.size(); ++i)
	{
		printf ("%lld ", arb[i].s_st);
	}
	printf ("\n\nsuma dreapta:\n");
	for (i = 1; i < arb.size(); ++i)
	{
		printf ("%lld ", arb[i].s_dr);
	}
	printf ("\n\nsuma maxima:\n");
	for (i = 1; i < arb.size(); ++i)
	{
		printf ("%lld ", arb[i].s_max);
	}
	return 0;
}

void solve()
{
	int m;
	FILE *fin = fopen("sequencequery.in", "r");
	FILE *fout = fopen("sequencequery.out", "w");
	fscanf(fin, "%d%d", &n, &m);
	arb.resize(4 * n);

	for (pos = 1; pos <= n; ++pos)
	{
		fscanf(fin, "%d", &val);
		update(1, 1, n);
	}
	
	for (; m; --m)
	{
		fscanf(fin, "%d%d", &seq_start, &seq_end);
		maxim = -100000;
		dreapta = -100000;
		query(1, 1, n);
		fprintf(fout, "%lld\n", maxim);
	}
	
	fclose(fin);
	fclose(fout);
}

void update(int nod, int st, int dr)
{
	if (st == dr)
	{
		arb[nod].s_st = arb[nod].s_dr = val;
		arb[nod].s_max = arb[nod].s_tot = val;
	}
	else
	{
		int mid = (st + dr) / 2;
		if (pos <= mid)
		{
			update(2 * nod, st, mid);
		}
		else
		{
			update(2 * nod + 1, mid + 1, dr);
		}
		arb[nod].s_tot = arb[2*nod].s_tot + arb[2*nod+1].s_tot;
		arb[nod].s_st = max(arb[2*nod].s_tot + arb[2*nod+1].s_st, arb[2*nod].s_st);
		arb[nod].s_dr = max(arb[2*nod+1].s_tot + arb[2*nod].s_dr, arb[2*nod+1].s_dr);
		arb[nod].s_max = max(arb[2*nod].s_max, arb[2*nod+1].s_max, arb[2*nod].s_dr + arb[2*nod+1].s_st);
	}
}
/*
void query(int nod, int st, int dr)
{
	if (st == seq_start && dr == seq_end)
	{
		maxim = arb[nod].s_max;
		return;
	}
	else
	{
		
	}
}
*/

void query(int nod, int st, int dr)
{
	if (seq_start <= st && dr <= seq_end)
	{
		maxim = max(maxim, arb[nod].s_max);
		maxim = max(maxim, dreapta + arb[nod].s_st);
		dreapta = max(arb[nod].s_dr, dreapta + arb[nod].s_tot);
	}
	else
	{
		int mid = (st + dr) / 2;
		if (seq_start <= mid)
		{
			query(2 * nod, st, mid);
		}
		if (mid < seq_end)
		{
			query(2 * nod + 1, mid + 1, dr);
		}
	}
}


inline ll max(ll a, ll b)
{
	return ((a > b) ? a : b);
}

inline ll max(ll a, ll b, ll c)
{
	a = max(a, b);
	return max(a, c);
}

inline ll max(ll a, ll b, ll c, ll d)
{
	a = max(a, b);
	c = max(c, d);
	return max(a, c);
}