#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 InfMin = LLONG_MIN;

struct node
{	
	// SumTot = suma din tot intervalul
	// SumMax = suma maxima din interval
	// st = subsecventa de suma maxima care se termina in st
	// dr = subsecventa de suma maxima care incepe in dr
	ll SumTot, SumMax = InfMin, st, dr;
};

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

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

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

	node ans;

	ans.SumTot = a.SumTot + b.SumTot;
	ans.SumMax = max(a.dr + b.st, a.SumMax, b.SumMax);
	ans.st = max(a.st, a.SumTot + b.st);
	ans.dr = max(b.dr, b.SumTot + a.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)
{
	// not included
	if (tr < ql || qr < tl)
	{
		return Null;
	}

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

	// partial included
	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';
	}
}