#include <fstream>
#include <algorithm>
#define DIM 100010
#define INF 2000000000

using namespace std;

class arb
{
public:
	long long m_best, m_max, m_min;
	arb()
	{
		m_best = m_max = m_min = 0;
	}
	arb(long long a, long long b, long long c)
	{
		m_best = a;
		m_max = b;
		m_min = c;
	}
};

int n, q;
arb aint[4 * DIM];
long long sum[DIM];
long long ans, Min;

inline int LeftSon(const int & x)
{
	return 2 * x;
}

inline int RightSon(const int & x)
{
	return 2 * x + 1;
}

void Build(int nod, int left, int right)
{
	if (left == right)
	{
		aint[nod] = arb(sum[left] - sum[left - 1], sum[left], sum[left]);
		return;
	}
	int mid = (left + right) / 2;
	Build(LeftSon(nod), left, mid);
	Build(RightSon(nod), mid + 1, right);
	aint[nod].m_best = max(aint[RightSon(nod)].m_max - aint[LeftSon(nod)].m_min, max(aint[LeftSon(nod)].m_best, aint[RightSon(nod)].m_best));
	aint[nod].m_max = max(aint[LeftSon(nod)].m_max, aint[RightSon(nod)].m_max);
	aint[nod].m_min = min(aint[LeftSon(nod)].m_min, aint[RightSon(nod)].m_min);
}

void Query(int nod, int left, int right, const int & LeftQuery, const int & RightQuery)
{
	if (LeftQuery <= left && right <= RightQuery)
	{
		ans = max(ans, max(aint[nod].m_best, aint[nod].m_max - Min));
		Min = min(Min, aint[nod].m_min);
		return;
	}
	int mid = (left + right) / 2;
	if (LeftQuery <= mid)
		Query(LeftSon(nod), left, mid, LeftQuery, RightQuery);
	if (RightQuery >= mid + 1)
		Query(RightSon(nod), mid + 1, right, LeftQuery, RightQuery);
}

int main()
{
	ifstream fin("sequencequery.in");
	ofstream fout("sequencequery.out");
	fin >> n >> q;
	int aux;
	for (int i = 1;i <= n;++i)
	{
		fin >> aux;
		sum[i] = sum[i - 1] + aux;
	}
	Build(1, 1, n);
	int x, y;
	for (int i = 1;i <= q;++i)
	{
		fin >> x >> y;
		ans = -INF;
		Min = sum[x - 1];
		Query(1, 1, n, x, y);
		fout << ans << "\n";
	}
	fin.close();
	fout.close();
	return 0;
}