#include <bits/stdc++.h>
 
using namespace std;
 
int n,m,ans;
int t[100003];
const int NMAX = 300003;
 
struct elem{
	long long seg,pref,suf,sum;
};
class segtree{
private:
    elem v[NMAX];
    elem NOTHING = {-INT_MAX,-INT_MAX};
public:
	elem combine(elem a,elem b){
		return{
			max(a.seg,max(b.seg,a.suf+b.pref) ),
			max(a.pref,a.sum+b.pref),
			max(b.suf,b.sum+a.suf),
			a.sum+b.sum
			
		};
	}
	elem single(int x){ // alone
		return {x,x,x,x};
		//return {0,0,0,x};
	}
	void build(int nod,int st,int dr){
		if(st==dr){
			v[nod]=single(t[st]);
			return ; 
		}
		int mid=(st+dr)>>1;
		build(2*nod,st,mid);
		build(2*nod+1,mid+1,dr);
		v[nod]=combine(v[2*nod],v[2*nod+1]);
	}
	void update(int nod,int st,int dr,int poz,int val){
		if(st==dr){
			v[nod]=single(val);
			return ;
		}
		int mid=(st+dr)>>1;
		if(poz<=mid)update(2*nod,st,mid,poz,val);
		else update(2*nod+1,mid+1,dr,poz,val);
		v[nod]=combine(v[2*nod],v[2*nod+1]);
	}
	elem query(int nod,int st,int dr,int x,int y){
		if(dr<x || st>y)return NOTHING;
		if(x<=st && dr<=y)return v[nod];
		int mid=(st+dr)>>1;
		elem left=query(2*nod,st,mid,x,y);
		elem right=query(2*nod+1,mid+1,dr,x,y);
		return combine(left,right);
	}
	
}sg;
 
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]);
	}
	sg.build(1,1,n);
	while(m--){
		int x,y;
		scanf("%d %d",&x,&y);
		
		printf("%lli\n",sg.query(1,1,n,x,y).seg );
		
	}
 
    return 0;
}