#include <bits/stdc++.h> 

using namespace std;

ifstream in;
ofstream out;

struct node {
	long long sum, prefixsum, suffixsum, maxsum;
};

vector<node> tree;

void build(int vert, int lf, int rg)
{
	if (lf == rg)
	{
		long long x;
		in >> x;
		tree[vert].sum = x;
		tree[vert].prefixsum = x;
		tree[vert].suffixsum = x;
		tree[vert].maxsum = x;
	}
	else
	{
		int mid = (lf + rg) / 2;
		build(vert * 2, lf, mid);
		build(vert * 2 + 1, mid + 1, rg);
		tree[vert].sum = tree[vert * 2].sum + tree[vert * 2 + 1].sum;
		tree[vert].prefixsum = max(tree[vert * 2].prefixsum, tree[vert * 2].sum + tree[vert * 2 + 1].prefixsum);
		tree[vert].suffixsum = max(tree[vert * 2 + 1].suffixsum, tree[vert * 2 + 1].sum + tree[vert * 2].suffixsum);
		tree[vert].maxsum = max(tree[vert].prefixsum, max(tree[vert].suffixsum, max(tree[vert * 2].maxsum, max(tree[vert * 2 + 1].maxsum, tree[vert * 2].suffixsum + tree[vert * 2 + 1].prefixsum))));
	}
}

node query(int vert, int lf,int rg, int a, int b)
{
	node result;
	result.sum = result.prefixsum =result.suffixsum =result.maxsum = LLONG_MIN;
	if (rg<a or lf>b)
		return result;
	if (a <= lf and rg <= b)
		return tree[vert];

	int mid = (lf + rg) / 2;
	
	if (a > mid)
		return query(vert * 2 + 1, mid + 1, rg, a, b);
	if (b <= mid)
		return query(vert * 2, lf, mid, a, b);


	node left = tree[vert*2];
	node right = tree[vert*2+1];
	
	result.sum = left.sum + right.sum;
	result.prefixsum = max(left.prefixsum, left.sum + right.prefixsum);
	result.suffixsum = max(right.suffixsum, right.sum + left.suffixsum);
	result.maxsum = max(result.prefixsum, max(result.suffixsum, max(left.maxsum, max(right.maxsum, left.suffixsum + right.prefixsum))));
	return result;
}

int n, m, a, b;

int main()
{
	in.open("sequencequery.in");
	out.open("sequencequery.out");

	in >> n >> m;
	tree.resize(4 * n + 5);
	build(1, 1, n);
	for (int i = 1; i <= m; i++)
	{
		in >> a >> b;
		out<<query(1, 1, n, a, b).maxsum<<'\n';
	}
}