#include<fstream>
#define INF 0x3f3f3f3f
#define NN 100001

using namespace std;
ofstream out("sequencequery.out");

int n,m,v[NN+1],ans;

void read();
void dinamica(int *v,int start,int end,int &ans);

int main()
{
	read();
	return 0;
}


void dinamica(int *v,int start,int end,int &ans)
{
	int sum=0,sbest=-INF;
	for(int i=start;i<=end;i++)
	{
		if(sum<0)
			sum=v[i];
		else
			sum+=v[i];
		
		if(sum>sbest)
			sbest=sum;
	}
	ans=sbest;
}

void read()
{
	ifstream in("sequencequery.in");
	in>>n>>m;
	for(int i=1;i<=n;i++)
		 in>>v[i];
	int A,B;
	for(int i=1;i<=m;i++)
	{
		in>>A>>B;
		dinamica(v,A,B,ans);
		out<<ans<<'\n';
	}
}