#include <stdio.h>
#include <algorithm>
#define nmax 100010

using namespace std;
typedef long long int ll;
struct date { ll mi,mx,best; };

int n,m,x,y;
ll cmin,val;
int t[nmax],sum[nmax];
date arb[3*nmax];

void build(int nod,int st,int dr)
{
	if (st==dr) {
		arb[nod].mi=sum[st-1];
		arb[nod].mx=sum[st]; 
		arb[nod].best=t[st];
		return;
	} else
	{
		int m=(st+dr)/2;
		build(nod*2,st,m);
		build(nod*2+1,m+1,dr);
		arb[nod].mi=min(arb[nod*2].mi,arb[nod*2+1].mi);
		arb[nod].mx=max(arb[nod*2].mx,arb[nod*2+1].mx);
		arb[nod].best=max(max(arb[nod*2].best,arb[nod*2+1].best),arb[nod*2+1].mx-arb[nod*2].mi);
	}
}

void query(int nod,int st,int dr,int x,int y)
{
	if (st>=x && dr<=y) {
		val=max(val,arb[nod].best);
		if (cmin<2e11) val=max(val,arb[nod].mx-cmin);
		cmin=min(cmin,arb[nod].mi);
		return;
	} else
	{
		int m=(st+dr)/2;
		if (x<=m) query(nod*2,st,m,x,y);
		if (y>m) query(nod*2+1,m+1,dr,x,y);
	}
}

int main()
{
	freopen("sequencequery.in","r",stdin);
	freopen("sequencequery.out","w",stdout);
	scanf("%d %d",&n,&m);
	for (int i=1;i<=n;i++) scanf("%d",&t[i]);
	for (int i=1;i<=n;i++) sum[i]=sum[i-1]+t[i];
	build(1,1,n);
	for (int i=1;i<=m;i++) {
		scanf("%d %d",&x,&y); cmin=2e11; val=-2e11;
		query(1,1,n,x,y);
		printf("%lld\n",val);
	}
	return 0;
}