#include <iostream>
#include <fstream>
using namespace std;

#define INF -0x3f3f3f3f

int x,y,sol,SMax,i,N,M,nr[100000],j,k,st,dr,poz;
int main()
{
	ifstream f("sequencequery.in");
	ofstream g("sequencequery.out");
	sol=INF;
	f>>N>>M;
	for (i=1;i<=N;++i)
		f>>nr[i];
	for (i=1;i<=M;++i)
	{
		SMax=0;
		sol=INF;
		f>>x>>y;
		for (j=x;j<=y;++j)
		{
			if (SMax<0)
			{
				SMax=nr[j];
				poz=j;
			}
			else SMax+=nr[j];
			if (SMax>sol)
			{
				sol=SMax;
				st=poz;
				dr=j;
			}
		}
		g<<sol<<"\n";
	}
	f.close();
	g.close();
	return 0;
}