#include <fstream>
#include <climits>
#include <vector>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <bitset>
#include <map>
#include <cstring>
#include <algorithm>
#define NMAX 200003
#define MOD 9973

using namespace std;



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

int n,m;
long long int v[NMAX];


struct nod {
	long long sumInterval;//suma de pe intreg intervalul
	long long prefixMaxim;//suma maxima a prefixului intervalului reprezentat de nodul asta
	long long sufixMaxim;//suma maxima a sufixului intervalului reprezentat de nodul asta
	long long subsecvMaxSum;//valoarea subsecventei de suma maxima a secventei curente
}arb[4*NMAX+3];

nod reuniuneIntervale(nod nodSt, nod nodDr)
{
	nod reuniune;
	reuniune.sumInterval = nodSt.sumInterval + nodDr.sumInterval;//adun sumele celor 2 intervale
	reuniune.prefixMaxim = max(nodSt.prefixMaxim, nodSt.sumInterval + nodDr.prefixMaxim);//maximul dintre prefixul nodului din stanga(ala care va fi prefix) si suma intervalului din dreapta+sufixul primului
	reuniune.sufixMaxim = max(nodDr.sufixMaxim, nodDr.sumInterval + nodSt.sufixMaxim);//ca mai sus doar ca fac invers pentru sufix
	reuniune.subsecvMaxSum = max(nodDr.prefixMaxim + nodSt.sufixMaxim, max(nodSt.subsecvMaxSum, nodDr.subsecvMaxSum));//aici imi iau maximul dintre ssm-uri si incerc sa vad daca reunind cele 2 intervale mi se schimba maximul
	return reuniune;
}


void build(int indexNod, int st, int dr)
{
	if (st == dr)
	{
		arb[indexNod] = { v[st],v[st],v[st],v[st] };//lungimea 1
		return;
	}
	else
	{
		int mij = (st + dr)/2;
		build(2 * indexNod, st, mij);
		build(2 * indexNod + 1, mij + 1, dr);
		arb[indexNod] = reuniuneIntervale(arb[2 * indexNod], arb[2 * indexNod + 1]);
	}
}

/*void update(int nod, int st, int dr, int poz)
{
	int mij;
	if (st == dr)
	{
		arb[nod] = { v[st],v[st],v[st],v[st] };
		return;
	}
	else
	{
		mij = (st + dr)/2;
		if (poz <= mij)
		{
			update(2 * nod, st, mij,poz);

		}
		else if (mij + 1 <= poz)
		{
			update(2 * nod + 1, mij + 1, dr,poz);
		}
		
		arb[nod] = reuniuneIntervale(arb[2 * nod], arb[2 * nod + 1]);
	}
}*/

nod query(int indexNod, int st, int dr, int qSt, int qDr)
{
	
	if (qSt <= st && dr <= qDr)
	{
		//sunt i
		return arb[indexNod];
	}
	else
	{
		int mij = (st + dr)/2;
		if (qDr <= mij)
		{
			return query(2 * indexNod, st, mij, qSt, qDr);//am doar in stanga
		}
		if (mij  < qSt)
		{
			return query(2 * indexNod + 1, mij + 1, dr, qSt, qDr);//am intervalul din dreapta
		}

		return reuniuneIntervale(query(2 * indexNod, st, mij, qSt, qDr), query(2 * indexNod + 1, mij + 1, dr, qSt, qDr));
	}
}


int main()
{

	fin >> n>>m;
	for (int i = 1; i <= n; i++)
	{
		fin >> v[i];
	}
	build(1, 1, n);
	//fin >> m;
	for (int i = 1; i <= m; i++)
	{
		//int cer;
		//fin >> cer;
		int st, dr;
		fin >> st >> dr;
		fout << query(1, 1, n, st, dr).subsecvMaxSum << "\n";
		/*if (cer == 0)
		{
			//update
			int a, b;
			fin >> a >> b;
			v[a] = b;
			update(1, 1, n, a);
		}
		else if (cer == 1)
		{
			
		}*/
	}
	return 0;
}