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

#define INF -0x3f3f3f3f
#define LIM 1000000

int i,j,N,M,x,y;
long long sol,s;
int v[LIM];
long long a[LIM],b[LIM],c[LIM],sum[LIM];

void build(int nod,int li,int ls)
{
	int mij=(li+ls)/2,st=nod*2,dr=st+1;
	if(li==ls)
	{
		a[nod]=v[li];
		b[nod]=v[li];
		c[nod]=v[li];
		sum[nod]=v[li];
	}
	else
	{
		build(st,li,mij);
		build(dr,mij+1,ls);

		a[nod]=max(a[st],sum[st]+a[dr]);
		b[nod]=max(b[dr],sum[dr]+b[st]);
		c[nod]=max(maxim(c[st],c[dr]),b[st]+a[dr]);
		sum[nod]=sum[st]+sum[dr];
	}
}

void query(int nod,int li,int ls)
{
	int mij=(li+ls)/2,st=nod*2,dr=st+1;
	if(x<=li&&y>=ls)
	{
		sol=max(maxim(a[nod],s+a[nod]),max(sol,c[nod]));
		s=max(b[nod],s+sum[nod]);
	}
	else
	{
	if(x<=mij)
		query(st,li,mij);
	if(y>mij)
		query(dr,mij+1,ls);
	}
}

int main(void)
{
	ifstream f("sequencequery.in");
	ofstream g("sequencequery.out");
	f>>N>>M;
	for(i=1;i<=N;++i)
		f>>v[i];
	build(1,1,n);
	i=i;
	for(i=1;i<=M;++i)
	{
		f>>x>>y;
		s=-32099;
		sol=-32044;
		query(1,1,n);
		g<<sol<<"\n";
	}
	f.close();
	g.close();
	return 0;
}