#include <bits/stdc++.h>
#define ll long long

std::ifstream f("sequencequery.in");
std::ofstream g("sequencequery.out");

struct node{
	ll int imn, imx, mn, mx;
};
	

const int SIZE=100000;
node a[SIZE*4+4];
ll int v[SIZE+1];

void makeSum(int n){
	for(int i=1;i<=n;i++)
		v[i]=v[i]+v[i-1];
}

node combine(node a, node b){
	node r=a;
	r.imx=a.imx;
	r.imn=a.imn;
	if(r.imx-r.imn<b.imx-b.imn){
		r.imx=b.imx;
		r.imn=b.imn;
	}
	if(r.imx-r.imn<b.imx-a.imn){
		r.imx=b.imx;
		r.imn=a.imn;
	}
	if(r.imx-r.imn<b.mx-a.mn){
		r.imx=b.mx;
		r.imn=a.mn;
	}
	r.mx=std::max(a.mx,b.mx);
	r.mn=std::min(a.mn,b.mn);
	return r;
}

void build(int n, int left, int right){
	if(left==right){
		int mn=std::min(v[left],v[left-1]);
		int mx=std::max(v[left],v[left-1]);
		a[n]={v[left-1],v[left],mn,mx};
		return;
	}
	int mid=(left+right)/2;
	build(n*2,left,mid);
	build(n*2+1,mid+1,right);
	a[n]=combine(a[n*2],a[n*2+1]);
}

node query(int n, int left, int right, int ql, int qr){
	if(ql<=left && right<=qr){
		return a[n];
	}
	int mid=(left+right)/2;
	node r, b;
	bool a=0;
	if(ql<=mid){
		r=query(n*2,left,mid,ql,qr);
		a=1;
	}
	if(mid<qr){
		b=query(n*2+1,mid+1,right,ql,qr);
		if(a)
			r=combine(r,b);
		else
			r=b;
	}
	return r;
}

int n,q;
int main(){
	f>>n>>q;
	for(int i=1;i<=n;i++)
		f>>v[i];
	makeSum(n);
	build(1,1,n);
	for(int i=1;i<=q;i++){
		int a, b;
		f>>a>>b;
		node m=query(1,1,n,a,b);
		g<<m.imx-m.imn<<'\n';
	}
	return 0;
}