#include <iostream>
#include <fstream>
#include <algorithm>
#include <limits.h>

#define ll long long

using namespace std;

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

const int N = 100005;
const ll Inf = LLONG_MAX;

struct node
{
	/*
		SumTot = suma totala din interval
		SumMax = suma maxima din interval
		st = suma maxima din secventa care incepe din st
		dr = suma maxima din secventa care se termina in dr
	*/
	ll SumTot, SumMax = Inf, st, dr;
};

int n, q;
ll v[N];
node arb[4 * N];
node NullElem;

ll max(ll a, ll b, ll c)
{
	return max(max(a, b), c);
}

node UpdateNode(node left, node right)
{
	if (left.SumMax == Inf)
	{
		return right;
	}
	else if (right.SumMax == Inf)
	{
		return left;
	}

	node ans;

	ans.SumTot = left.SumTot + right.SumTot;
	ans.SumMax = max(left.dr + right.st, left.SumMax, right.SumMax);
	ans.st = max(left.st, left.SumTot + right.st);
	ans.dr = max(right.dr, right.SumTot + left.dr);

	return ans;
}

void build(int tl = 1, int tr = n, int ti = 1)
{
	if (tl == tr)
	{
		arb[ti].SumTot = arb[ti].SumMax = arb[ti].st = arb[ti].dr = v[tl];
		return;
	}

	int mid = (tl + tr) / 2;
	build(tl, mid, ti * 2);
	build(mid + 1, tr, ti * 2 + 1);
	arb[ti] = UpdateNode(arb[ti * 2], arb[ti * 2 + 1]);
}

node query(int ql, int qr, int tl = 1, int tr = n, int ti = 1)
{
	if (tr < ql || qr < tl)
	{
		return NullElem;
	}

	if (ql <= tl && tr <= qr)
	{
		return arb[ti];
	}

	int mid = (tl + tr) / 2;
	node r1 = query(ql, qr, tl, mid, ti * 2);
	node r2 = query(ql, qr, mid + 1, tr, ti * 2 + 1);
	return UpdateNode(r1, r2);
}

int main()
{
	fin >> n >> q;

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

	build();

	while (q--)
	{
		int x, y;
		fin >> x >> y;
		fout << query(x, y).SumMax << '\n';
	}
}