#include<fstream>
using namespace std;
ifstream f("sequencequery.in");
ofstream g("sequencequery.out");
int a[100001];
int caut(int x, int y)
{
	int i,best,min=0,r=0;
	int sum=0;
	best=-9999999;
	for (i=x;i<=y;i++)
	{
		r+=a[i];
		sum=r-min;
		if (r<min) min=r;
		if (sum>best) best=sum;
	}
	if (x==y) return a[x];
	else return best;
}
int main()
{
	int n,i,k;
	f>>n>>k;
	for (i=1;i<=n;i++)
		f>>a[i];
	for (i=1;i<=k;i++)
	{
		int x,y;
		f>>x>>y;
		g<<caut(x,y)<<'\n';
	}
	return 0;
}