//https://infoarena.ro/problema/sequencequery
//#pragma GCC optimize ("Ofast")
//#pragma GCC optimize ("fast-math")
//#pragma GCC optimize ("unroll-loops")
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;

ifstream fin("sequencequery.in");
ofstream fout("sequencequery.out");

struct arbore
{
	int m;//subsecventa de suma maxima
	int st;
	int dr;
	int sum;//sum totala
};
arbore arb[1000005];
int v[100005];
void init(int x, int in, int sf)
{
	//cout << x << " " << in << " " << sf << "\n";
	if (in == sf)
	{
		arb[x].m = v[in];
		arb[x].st = v[in];
		arb[x].dr = v[in];
		arb[x].sum = v[in];
		return;
	}

	int ls = x * 2;
	int rs = ls + 1;

	init(ls, in, (in + sf) / 2);
	init(rs, (in + sf) / 2 + 1, sf);

	arb[x].m = max(max(arb[ls].m, arb[rs].m), (arb[ls].dr + arb[rs].st));
	arb[x].st = max(arb[ls].st, (arb[ls].sum + arb[rs].st));
	arb[x].dr = max(arb[rs].dr, (arb[rs].sum + arb[ls].dr));
	arb[x].sum = arb[ls].sum + arb[rs].sum;
}
void rezultat(int x, int in, int sf, int a, int b, int& rez, int& maxi)
{
	//cout << x << " " << in << " " << sf << " " << a << " " << b << " " << rez << " " << maxi << "\n";
	if (b < in || sf < a)
	{
		return;
	}

	if (a <= in && sf <= b)
	{
		rez = max(rez, max(arb[x].m, maxi + arb[x].st));
		maxi = max(maxi + arb[x].sum, arb[x].dr);
		return;
	}

	int ls = x * 2;
	int rs = ls + 1;

	rezultat(ls, in, (in + sf) / 2, a, b, rez, maxi);
	rezultat(rs, (in + sf) / 2 + 1, sf, a, b, rez, maxi);
}
int main()
{
	ios_base::sync_with_stdio(false);
	//cin.tie(NULL);

	int n, m, i, a, b;
	fin >> n >> m;

	for (i = 1; i <= n; ++i)
	{
		fin >> v[i];
	}

	init(1, 1, n);

	/*for (int i = 1; i <= n; ++i)
		cout << arb[i].m << " ";*/
	for (i = 1; i <= m; ++i)
	{
		fin >> a >> b;

		int rez = -100005, maxi = -100005;
		rezultat(1, 1, n, a, b, rez, maxi);

		fout << rez << "\n";
		//cout << "\n";
	}

	return 0;
}