#define REP(a,b) for(int a=0; a<(b); ++a)
#define FWD(a,b,c) for(int a=(b); a<(c); ++a)
#define FWDS(a,b,c,d) for(int a=(b); a<(c); a+=d)
#define BCK(a,b,c) for(int a=(b); a>(c); --a)
#define ALL(a) (a).begin(), (a).end()
#define SIZE(a) ((int)(a).size())
#define VAR(x) #x ": " << x << " "
#define FILL(x,y) memset(x,y,sizeof(x))
#define MIN(a,b) (((a)<(b))?(a):(b))
#define MAX(a,b) (((a)>(b))?(a):(b))
#define x first
#define y second
#define st first
#define nd second
#define pb push_back
#define l(n) (n<<1)
#define r(n) ((n<<1)+1)
#define f(n) (n>>1)
#define lsb(a) (a&-a)
 
#include<vector>
#include<string.h>
#include<queue>
 
using namespace std;

#include<fstream>
ifstream cin("sequencequery.in");
ofstream cout("sequencequery.out");
 
const int NMAX = 1e5;
const int INF = 0x3f3f3f3f;
const int dx[] = {0,0,-1,1}; //1,1,-1,1};
const int dy[] = {-1,1,0,0}; //1,-1,1,-1};
 
typedef long long LL;
typedef pair<int, int> PII;
typedef long double K;
typedef pair<K, K> PKK;
typedef vector<int> VI;

struct Node{
	int sum, pref, suff, max;
};

Node make_node(int val)
{
	Node n;
	n.sum = val;
	n.pref=n.suff=n.max=val;
	return n;
}

Node combine(Node l, Node r)
{
	Node n;
	n.sum=r.sum+l.sum;
	n.pref=MAX(l.pref, l.sum+r.pref);
	n.suff=MAX(r.suff, l.suff+r.sum);
	n.max = MAX(MAX(l.max, r.max), l.suff + r.pref);
	return n;
}

int N;
Node Arb[4*NMAX];
int A[NMAX];


/*
int Pos, Val;
void _update(int n, int left, int right)
{
	
	if(left==right)
	{
		Arb[n]=make_node(Val);
		return;
	}
	int pivot=(left+right)>>1;
	if(Pos>pivot)
		_update(r(n), pivot+1, right);
	else
		_update(l(n), left, pivot);
	
	Arb[n] = combine(Arb[l(n)], Arb[r(n)]);
}
void Update(int x, int y)
{
	Pos=x;
	Val=y;
	_update(1,1,N);
}
*/

Node _query(int n, int left, int right, int a, int b)
{
	if(a==left && right==b)
		return Arb[n];
		
	int pivot=(left+right)>>1;
	if(b<=pivot)
		return _query(l(n), left, pivot, a, b);
	if(a>pivot)
		return _query(r(n), pivot+1, right, a, b);
	
	return combine(
		_query(l(n), left, pivot, a, pivot),
		_query(r(n), pivot+1, right, pivot+1, b)
	);
}

void _build(int n, int left, int right)
{
	if(left==right){
		Arb[n]=make_node(A[left]);
		return;
	}
	int pivot=(left+right)>>1;
	_build(l(n), left, pivot);
	_build(r(n), pivot+1, right);
	
	Arb[n] = combine(Arb[l(n)], Arb[r(n)]);
}

int n,m;

int main()
{
	cin>>n>>m;
	N=n;
	REP(i,n)
	{
		int a;
		cin>>A[i+1];
	}
	_build(1,1,N);
	
	REP(i,m)
	{
		int x,y;
		cin>>x>>y;
		cout<<_query(1,1,N,x,y).max<<"\n";
	}
	return 1;
}