#include <iostream>
#include <fstream>

using namespace std;

ifstream f("sequencequery.in");
ofstream g("sequencequery.out");

const int NMAX = 1e5;

struct Node
{
	long long sum;
	long long prefmax;
	long long suffmax;
	long long smax;
};

int v[NMAX + 1];
Node aint[NMAX * 4 + 1];
int N, M, x, y;

Node combine(Node L, Node R)
{
	Node T;
	T.sum = L.sum + R.sum;
	T.prefmax = max(L.prefmax, L.sum + R.prefmax);
	T.suffmax = max(R.suffmax, L.suffmax + R.sum);
	T.smax = max(max(L.smax, R.smax), L.suffmax + R.prefmax);
	return T;
}

void build(int node, int st, int dr)
{
	if (st == dr)
	{
		aint[node].sum = v[st];
		aint[node].prefmax = v[st];
		aint[node].suffmax = v[st];
		aint[node].smax = v[st];
	}
	else
	{
		int mid = (st + dr) >> 1;
		build(node << 1, st, mid);
		build(node << 1 | 1, mid + 1, dr);
		aint[node] = combine(aint[node << 1], aint[node << 1 | 1]);
	}
}

Node query(int node, int st, int dr, int x, int y)
{
	if (x <= st && dr <= y)
		return aint[node];
	else
	{
		int mid = (st + dr) >> 1;
		if (y <= mid)
			return query(node << 1, st, mid, x, y);
		if (mid < x)
			return query(node << 1 | 1, mid + 1, dr, x, y);
		Node L = query(node << 1, st, mid, x, y);
		Node R = query(node << 1 | 1, mid + 1, dr, x, y);
		return combine(L, R);
	}
}

int main()
{
	f >> N >> M;
	for (int i = 1; i <= N; i++)
		f >> v[i];
	build(1, 1, N);
	while (M--)
	{
		f >> x >> y;
		g << query(1, 1, N, x, y).smax << '\n';
	}
    f.close();
    g.close();
    return 0;
}