#include<stdio.h>
#define infile "sequencequery.in"
#define outfile "sequencequery.out"
#define nmax (400*1001)
#define inf ~(1<<31)
struct arb
{
	int min; //valoarea minima din interval
	int max; //valoarea maxima din interval
	int best; //subsecventa de suma maxima
}a[nmax];
int v[nmax]; //vectorul cu elementele
int n; //numarul de elemente din arbore
int m; //numarul de query-uri
int qmin; //valoarea minima la fiecare query

inline int min(int a, int b)
{
	if(a<b) return a; return b;
}

inline int max(int a, int b)
{
	if(a>b) return a; return b;
}

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

void init()
{
	int i;
	
	for(i=1;i<=n;i++)
		v[i]+=v[i-1];
}

void construct_arb(int rad, int st, int dr)
{
	a[rad].best=a[rad].max=-inf; a[rad].min=inf;
	if(st==dr)
	{
		a[rad].best=v[st]-v[st-1];
		a[rad].min=a[rad].max=v[st];
		return;
	}
	int mij=(st+dr)>>1;
	if(st<=mij) construct_arb(rad<<1,st,mij);
	if(mij<dr) construct_arb((rad<<1)|1,mij+1,dr);
	a[rad].min=min(a[rad<<1].min,a[(rad<<1)|1].min);
	a[rad].max=max(a[rad<<1].max,a[(rad<<1)|1].max);
	a[rad].best=max(a[(rad<<1)|1].max-a[rad<<1].min,max(a[rad<<1].best,a[(rad<<1)|1].best));
}

int query(int rad, int st, int dr, int p, int q)
{
	if(p<=st && dr<=q)
	{
		int r=a[rad].best;
		if(qmin!=inf) r=max(r,a[rad].max-qmin);
		qmin=min(qmin,a[rad].min);
		return r;
	}
	int mij=(st+dr)>>1;
	if(p<=mij && mij<q)
	{
		int r=query(rad<<1,st,mij,p,q);
		r=max(r,query((rad<<1)|1,mij+1,dr,p,q));
		return r;
	}
	else if(p<=mij) return query(rad<<1,st,mij,p,q);
	else return query((rad<<1)|1,mij+1,dr,p,q);
}

void solve()
{
	int st,dr;
	while(m--)
	{
		qmin=inf;
		scanf("%d %d\n",&st,&dr);
		printf("%d\n",query(1,1,n,st,dr));
	}
}

int main()
{
	freopen(infile,"r",stdin);
	freopen(outfile,"w",stdout);
	
	read();
	init();
	construct_arb(1,1,n);
	solve();
	
	fclose(stdin);
	fclose(stdout);
	return 0;
}