# include <fstream>
# include <iostream>
# define DIM 100003
using namespace std;
struct arb{
	int m, M;
}a[2*DIM];
int n, m, s[DIM];
ifstream fin ("sequencequery.in");

void upd(int k, int st, int dr, int p)
{
	if (st>=dr)
	{
		a[k].m=p-1;
		a[k].M=p;
		return;
	}
	int mij=(st+dr)/2;
	if (p<=mij)
		upd(2*k,st,mij,p);
	else
		upd(2*k+1, mij+1, dr, p);
	int m, M, m1=a[2*k].m, m2=a[2*k+1].m, M1=a[2*k].M, M2=a[2*k+1].M;
	if (s[M1]-s[m1]>=s[M2]-s[m1] && s[M1]-s[m1]>=s[M2]-s[m2])
		M=M1, m=m1;
	else if (s[M2]-s[m1]>=s[M1]-s[m1] && s[M2]-s[m1]>=s[M2]-s[m2])
		M=M2, m=m1;
	else if (s[M2]-s[m2]>=s[M1]-s[m1] && s[M2]-s[m2]>=s[M2]-s[m1])
		M=M2, m=m2;
	a[k].m=m;a[k].M=M;	
}

void read ()
{	
	fin>>n>>m;
	int x;
	for(int i=1;i<=n;++i)
	{
		fin>>x;
		s[i]=s[i-1]+x;
		upd(1, 1, n, i);
	}
}

arb query(int k, int st, int dr, int i, int j)
{
	if (st>=i && dr<=j)
		return a[k];
	int mij=(st+dr)/2, l=0, r=0;
	arb x, y;
	if (i<=mij)x=query(2*k, st, mij, i, j), l=1;
	if (j>mij)y=query(2*k+1, mij+1, dr, i, j), r=1;
	if (l && !r)return x;
	if (!l && r)return y;
	int m, M, m1=x.m, m2=y.m, M1=x.M, M2=y.M;
	if (s[M1]-s[m1]>s[M2]-s[m1] && s[M1]-s[m1]>s[M2]-s[m2])
		M=M1, m=m1;
	else if (s[M2]-s[m1]>s[M1]-s[m1] && s[M2]-s[m1]>s[M2]-s[m2])
		M=M2, m=m1;
	else if (s[M2]-s[m2]>s[M1]-s[m1] && s[M2]-s[m2]>s[M2]-s[m1])
		M=M2, m=m2;
	x.m=m;x.M=M;	
	return x;
}

void solve ()
{
	freopen("sequencequery.out", "w", stdout);
	int x, y;
	arb r;
	for(;m--;)
	{
		fin>>x>>y;
		r=query(1, 1, n, x, y);
		printf("%d\n",s[r.M]-s[r.m]);
	}
}			

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