#include <fstream>
#include <algorithm>

using namespace std;

struct AINT
{
	long long max, min, best;
};

const int NMAX = 100010;
const long long INF = (1LL << 61);
int n, q;
long long sum[NMAX];
long long v[NMAX];
AINT aint[4 * NMAX];
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 node, int left, int right)
{
	if (left == right)
	{
		aint[node].max = aint[node].min = sum[left];
		aint[node].best = sum[left] - sum[left - 1];
		return;
	}
	int mid = (left + right) / 2;
	Build(LeftSon(node), left, mid);
	Build(RightSon(node), mid + 1, right);
	aint[node].best = max(max(aint[LeftSon(node)].best, aint[RightSon(node)].best), aint[RightSon(node)].max - aint[LeftSon(node)].min);
	aint[node].max = max(aint[LeftSon(node)].max, aint[RightSon(node)].max);
	aint[node].min = min(aint[LeftSon(node)].min, aint[RightSon(node)].min);
}

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

int main()
{
	ifstream fin("sequencequery.in");
	ofstream fout("sequencequery.out");
	fin >> n >> q;
	int x, y;
	for (int i = 1;i <= n;++i)
	{
		fin >> x;
		v[i] = x;
		sum[i] = 1LL * sum[i - 1] + x;
	}
	Build(1, 1, n);
	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;
}