#include<iostream>
#include<fstream>

#define nm 100005
#define inf 1<<30
using namespace std;

long long v[nm],n,m;

ifstream f("ssm.in");
ofstream g("ssm.out");

struct interval
{
	int x,y;
	int s;
}a[nm];

int Max(int x,int y)
{
	if(x<=y)
		return y;
	return x;
}
int Max2(int x,int y,int z)
{
	if(x>=y&&x>=z)
		return x;
	if(y>=x&&y>=z)
		return y;
	if(z>=x&&z>=y)
		return z;
}

int detSecv(int c,int b)
{
	int max=-inf;
	if(c!=b&&c<b)
	{
		int s=0;
		for(int i=c;i<=b;++i)
			if(i!=b)
				s=Max(s+v[i],v[i]);
			else
				s=Max2(s,s+v[i],v[i]);
		return s;
	}
	else if(c==b)
		return v[c];
}

int main()
{
	f>>n>>m;
	for(int i=1;i<=n;++i)
		f>>v[i];
	for(int i=1;i<=m;++i)
		f>>a[i].x>>a[i].y;
	for(int i=1;i<=m;++i)
		a[i].s=detSecv(a[i].x,a[i].y);
	for(int i=1;i<=m;++i)
		g<<a[i].s<<endl;
}