#include <fstream>

using namespace std;

const char InFile[]="sequencequery.in";
const char OutFile[]="sequencequery.out";
const int aint_SIZE=1<<18;
const long long LLINF=1LL<<60;

ifstream fin(InFile);
ofstream fout(OutFile);

struct s_aint_node
{
	long long L,R,S,A;
};

int N,M,x,st,sf;
s_aint_node aint[aint_SIZE];

int update_pos,update_val,query_st,query_dr;
long long query_result,query_prefix;

inline int father(const int &nod)
{
	return nod>>1;
}

inline int left(const int &nod)
{
	return nod<<1;
}

inline int right(const int &nod)
{
	return (nod<<1)+1;
}

void update_aint(int st,int dr,int nod)
{
	if(st>dr)
	{
		return;
	}
	if(st==dr)
	{
		aint[nod].A=aint[nod].L=aint[nod].R=aint[nod].S=update_val;
		return;
	}
	int l=left(nod);
	int r=right(nod);
	int m=st+((dr-st)>>1);
	if(update_pos<=m)
	{
		update_aint(st,m,l);
	}
	if(update_pos>m)
	{
		update_aint(m+1,dr,r);
	}

	aint[nod].L=max(aint[l].L,aint[l].S+aint[r].L);
	aint[nod].R=max(aint[r].R,aint[r].S+aint[l].R);
	aint[nod].A=max(max(aint[l].A,aint[r].A),aint[l].R+aint[r].L);
	aint[nod].S=aint[l].S+aint[r].S;
}

inline void update(const int &pos, const int &val)
{
	update_pos=pos;
	update_val=val;
	update_aint(1,N,1);
}

void query(int st,int dr,int nod)
{
	if(query_st<=st && dr<=query_dr)
	{
		query_result=max(query_result,max(aint[nod].A,query_prefix+aint[nod].L));
		query_prefix=max(aint[nod].R,query_prefix+aint[nod].S);
		return;
	}
	int l=left(nod);
	int r=right(nod);
	int m=st+((dr-st)>>1);
	if(query_st<=m)
	{
		query(st,m,l);
	}
	if(query_dr>m)
	{
		query(m+1,dr,r);
	}
}

inline long long query(const int &st, const int &dr)
{
	query_st=st;
	query_dr=dr;
	query_result=query_prefix=-LLINF;
	query(1,N,1);
	return query_result;
}

int main()
{
	fin>>N>>M;
	for(register int i=1;i<=N;++i)
	{
		fin>>x;
		update(i,x);
	}
	for(register int i=1;i<=M;++i)
	{
		fin>>st>>sf;
		fout<<query(st,sf)<<"\n";
	}
	fin.close();
	fout.close();
	return 0;
}