//----------------------------------------------------------
// st[i] - subsecv. de suma max. de la inceputul interv.
// dr[i] - subsecv. de suma max. de la sf. interv.
// sum[i] - suma pe interv.
// best[i] - subsecv. de suma max. din interv.
//----------------------------------------------------------

#include<stdio.h>
#define  INF 1LL<<62

const int N=200002;
const int HN=3*N;
long long n,m,v[N],poz[N];
long long st[HN];
long long dr[HN];
long long sum[HN];
long long best[HN];

inline long long m2( long long a, long long b) {
	return( a>b ? a:b );
}

inline long long m3( long long a, long long b, long long c) {
	b=(b>c?b:c);
	return (a>b?a:b);
}

void Read()
{
	scanf("%d%d",&n,&m);
	for( int i=1; i<=n; ++i)
		scanf("%lld",&v[i]);
}

void GenerateTree( int lf, int rt, int nod)
{
	if( lf==rt )
	{
		poz[lf]=nod;
		st[nod]=dr[nod]=sum[nod]=best[nod]=v[lf];
		return;
	}
	int mid=(lf+rt)/2;
	GenerateTree( lf, mid, 2*nod);
	GenerateTree( mid+1, rt, 2*nod+1);
}

void Update(int nod)
{
	while(nod)
	{
		st[nod]=m2( st[2*nod] , sum[2*nod]+st[2*nod+1] );
		dr[nod]=m2( dr[2*nod+1] , sum[2*nod+1]+dr[2*nod] );
		sum[nod]= sum[2*nod]+sum[2*nod+1];
		best[nod]= m3( best[2*nod] , best[2*nod+1] , dr[2*nod]+st[2*nod+1] );
		nod/=2;
	}
}

void UpdateTree()
{
	for( int i=1; i<=n; i+=2)
		Update(poz[i]/2);
}

long long Result,Value,x,y;

void Query( int lf, int rt, int nod)
{
	if( lf>y || rt<x )
		return;
	if( lf>=x && rt<=y )
	{
		Result=m3(Result,best[nod],st[nod]+Value );
		Value=m2(Value+sum[nod],dr[nod]);
		return;
	}
	if( lf==rt )
		return;
	int mid=(lf+rt)/2;
	Query(lf,mid,2*nod);
	Query(mid+1,rt,2*nod+1);
}

int main()
{
	freopen("sequencequery.in","r",stdin);
	freopen("sequencequery.out","w",stdout);
	
	Read();
	
	GenerateTree(1,n,1);
	
	UpdateTree();
	
	//---------
	//Queries
	//---------
	
	while(m--)
	{
		scanf("%d%d",&x,&y);
		
		Result=-INF;
		Value=0;
		
		Query(1,n,1);
		
		printf("%lld\n",Result);
	}
	
	return 0;
}