rt

#include<bits/stdc++.h>

using namespace std;

typedef int ll;
typedef double db;

const int N=4*1e5+50;
inline int read()
{
	int x=0,f=1;char ch=getchar();
	while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
	while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
	return x*f;
}

ll a[N],ans[N];
ll lazy_add[N];
ll maxn[N];

ll ls(ll p){return p<<1;}
ll rs(ll p){return p<<1|1;}
void push_up(ll p){
	ans[p]=ans[ls(p)]+ans[rs(p)];
	maxn[p]=max(maxn[ls(p)],maxn[rs(p)]);
}

void build(ll p,ll l,ll r){
	lazy_add[p]=0;
	if(l==r) {ans[p]=a[l];maxn[p]=a[l];return;}
	ll mid=(l+r)>>1;
	build(ls(p),l,mid);
	build(rs(p),mid+1,r);
	push_up(p);
}

void change(ll p,ll l,ll r,ll add){
	ans[p]=ans[p]+(r-l+1)*add;
	lazy_add[p]=lazy_add[p]+add;
	maxn[p]=maxn[p]+add;
}
void push_down(ll p,ll l,ll r){
	ll mid=(l+r)>>1;
	change(ls(p),l,mid,lazy_add[p]);
	change(rs(p),mid+1,r,lazy_add[p]);
	lazy_add[p]=0;
}
ll query(ll nx,ll ny,ll l,ll r,ll p){
	ll res=0;
	if(nx<=l&&r<=ny) return maxn[p];
	push_down(p,l,r);
	ll mid=(l+r)>>1;
	if(nx<=mid) res=max(res,query(nx,ny,l,mid,ls(p)));
	if(ny>mid) res=max(res,query(nx,ny,mid+1,r,rs(p)));
	return res;
}
int main()
{
	ll n,m;
	n=read(),m=read();
	for(int i=1;i<=n;++i) a[i]=read();
	build(1,1,n);
	for(int i=1;i<=m;++i){
		ll x,y;
		x=read(),y=read();
		printf("%d\n",query(x,y,1,n,1));
	}
	return 0;
}