#include<cstdio>
#include<algorithm>
using namespace std;

int n,m,i,a,b,R,SOL,V[100010];

struct tree
{
	int val;
	int left;
	int right;
}arb[300010];

void read(),solve(),init(int,int,int,int,int),query(int,int,int,int,int);

int main()
{
	read();
	solve();
	
	return 0;
}

void read()
{
	freopen("sequencequery.in","r",stdin);
	freopen("sequencequery.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(i=1;i<=n;i++)
	{
		scanf("%d",&V[i]);
		V[i]+=V[i-1];
		init(1,1,n,i,V[i]-V[i-1]);
	}
}

void solve()
{
	for(;m--;)
	{
		scanf("%d%d",&a,&b);
		SOL=-(1<<30);
		R=0;
		query(1,1,n,a,b);
		printf("%d\n",SOL);
	}
}

void init(int nod,int left,int right,int pos, int val)
{
	if(pos<left || pos>right)return;
	if(left==right)
	{
		arb[nod].val=val;
		arb[nod].left=val;
		arb[nod].right=val;
		return ;
	}
	
	int mid=(left+right)/2;
	
	init(nod*2,left,mid,pos,val);
	init(nod*2+1,mid+1,right,pos,val);
	
	arb[nod].val=max(arb[nod*2].val,arb[nod*2+1].val);
	arb[nod].val=max(arb[nod].val,arb[nod*2].right+arb[nod*2+1].left);
	
	arb[nod].left=max(arb[nod*2].left,V[mid]-V[left-1]+arb[nod*2+1].left);
	
	arb[nod].right=max(arb[nod*2+1].right,V[right]-V[mid]+arb[nod*2].right);
}

void query(int nod,int left,int right,int a,int b)
{
	if(a<=left && right<=b)
	{
		if(SOL< arb[nod].val)SOL=arb[nod].val;
		if(SOL< R+arb[nod].left)SOL=R+arb[nod].left;
		if(arb[nod].right==V[right]-V[left-1] && R>0)R+=arb[nod].right;
		else R=arb[nod].right;
		return;
	}
	
	int mid=(left+right)/2;
	
	if(a<=mid)query(nod*2,left,mid,a,b);
	if(mid<b) query(nod*2+1,mid+1,right,a,b);
	
}