#include<fstream>
#define DIM 100004
using namespace std;
int mi[6*DIM],ma[6*DIM],a,b;
int sum[100003],n,m,v[100003],poz,maxim,minim;
void cautami(int nod,int st,int dr);
void cautama(int nod,int st,int dr);
void updatema(int nod,int st,int dr);
void updatemi(int nod,int st,int dr);
ofstream fout("sequencequery.out");
int main()
{
	ifstream fin("sequencequery.in");
	fin>>n>>m;
	int i,j;
	for(i=1;i<=n;i++)
	   fin>>v[i];
	for(i=1;i<=n;i++)
	{
		sum[i]=sum[i-1]+v[i];
		poz=i;
		updatema(1,1,n);
		updatemi(1,1,n);   
	}   
    for(i=1;i<=m;i++)
    {
		fin>>a>>b;
		maxim=0;minim=1238923;
		cautama(1,1,n);
		//fout<<maxim<<" ";
		int maxi=maxim-sum[a-1];
		cautami(1,1,n);
		//fout<<minim<<endl;
		int mini=minim-sum[a-1];
		if(a==b)
		  fout<<v[a]<<"\n";
		else
		     fout<<maxi-mini<<"\n";
		    
	 }
	 return 0;
 }
void updatema(int nod,int st,int dr)
 {
	 if(st==dr)
	 {
	    ma[nod]=sum[poz];
	    //fout<<st<<endl;
	    return;
	 }
	 else
	 {
		 int mij=(st+dr)/2;
		 if(poz<=mij)
		   updatema(2*nod,st,mij);
		 else
		   updatema(2*nod+1,mij+1,dr);
	  }
	  if(ma[2*nod]>ma[2*nod+1])
		 ma[nod]=ma[2*nod];
	  else
		 ma[nod]=ma[2*nod+1];
 }
 void updatemi(int nod,int st,int dr)
 {
	 if(st==dr)
	 {
	    mi[nod]=sum[poz];
	    return;
	 }
	 else
	 {
		 int mij=(st+dr)/2;
		 if(poz<=mij)
		   updatemi(2*nod,st,mij);
		 else
		   updatemi(2*nod+1,mij+1,dr);
		 if(mi[2*nod]<mi[2*nod+1])
		    mi[nod]=mi[2*nod];
		 else
		    mi[nod]=mi[2*nod+1];
	 }
 }
 void cautama(int nod,int st,int dr)
 {
	 if(a<=st && b>=dr)
	 {
		 if(maxim<ma[nod])
		   maxim=ma[nod];
		 return;
	 }
	 else
	 {
		 int mij=(st+dr)/2;
		 if(a<=mij)
		   cautama(2*nod,st,mij);
		 if(b>mij)
		   cautama(2*nod+1,mij+1,dr);
	  }
}
void cautami(int nod,int st,int dr)
 {
	 if(a<=st && b>=dr)
	 {
		 if(minim>mi[nod])
		   minim=mi[nod];
		 return;
	 }
	 else
	 {
		 int mij=(st+dr)/2;
		 if(a<=mij)
		   cautami(2*nod,st,mij);
		 if(b>mij)
		   cautami(2*nod+1,mij+1,dr);
	  }
}