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

using namespace std;

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

const int N = 100005, InfMin = INT_MIN;

struct node
{	
	// SumMax din interval
	// st = cat mai trb sa scazi ca sa ajungi la SumMax respectiva la stanga
	// dr = cat mai trb sa scazi ca sa ajungi la SumMax respectiva la dreapta
	int SumMax = InfMin, st = InfMin, dr = InfMin;
};

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

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

node UpdateNode(node a, node b)
{
	if (b.SumMax == InfMin)
	{
		return a;
	}
	else if (a.SumMax == InfMin)
	{
		return b;
	}

	node rez;
	int unire = a.SumMax + b.SumMax + a.dr + b.st;
	rez.SumMax = max(a.SumMax, b.SumMax, unire);

	if (rez.SumMax == unire)
	{
		rez.st = a.st;
		rez.dr = b.dr;
	}
	else if (rez.SumMax == a.SumMax)		// check order (ti * 2 OR ti * 2 + 1)
	{
		rez.st = a.st;
		rez.dr = b.st + b.SumMax + b.dr;
	}
	else
	{
		rez.dr = b.dr;
		rez.st = a.st + a.SumMax + a.dr;
	}
	return rez;
}

void build(int tl = 1, int tr = n, int ti = 1)
{
	if (tl == tr)
	{
		arb[ti].SumMax = v[tl];
		arb[ti].st = arb[ti].dr = 0;
		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 Null;
	}

	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;

		// subsecventa max din [x, y]
		fout << query(x, y).SumMax << '\n';
	}
}