#include <cstdio>
#include <algorithm>

using namespace std;


const int Dim = 100001,Inf = 0x3f3f3f3f;
int TreeM[Dim * 4],n,m,Treem[Dim * 4],S[Dim],mi,ma;

void Get(int &x);
void UpdateM(int node, int le,int ri,int pos ,int val) ;
void Updatem(int node, int le,int ri,int pos ,int val);
void Query(int node , int le , int ri , int a , int b);

int  main() {
		
	freopen("sequencequery.in","r",stdin);
	freopen("sequencequery.out","w",stdout);
	Get(n); Get(m);
	int x,y;
	for ( int i = 1; i <= n; ++i) {
		Get(x);
		
		S[i] = S[i-1] + x;
	}
	for ( int i = 1; i <= n; ++i) {
		UpdateM(1,1,n,i,S[i]);
		Updatem(1,1,n,i,S[i]);
		}
	for ( int i = 1; i <= m; ++i) {
		Get(x),Get(y);
		mi = Inf;
		ma = -Inf;
		if ( x != y) {
			Query(1,1,n,x,y);
			printf("%d\n",ma-mi); 	
			}
		else
			printf("%d\n",S[x] - S[x-1]); 
		}
		
}


void UpdateM(int node, int le,int ri,int pos ,int val) {
	if(le == ri) {
		TreeM[node] = val;
		return ;
	}
	int mj = (le + ri) / 2;
	if( pos <= mj)
		UpdateM(node * 2, le, mj , pos , val);
	else
		UpdateM(node * 2 + 1 , mj + 1 , ri , pos , val);
	TreeM[node]  = max( TreeM[node * 2]  , TreeM[node * 2 + 1] );
}

void Updatem(int node, int le,int ri,int pos ,int val) {
	if(le == ri) {
		Treem[node] = val;
		return ;
	}
	int mj = (le + ri) / 2;
	if( pos <= mj)
		Updatem(node * 2, le, mj , pos , val);
	else
		Updatem(node * 2 + 1 , mj + 1 , ri , pos , val);
	Treem[node]  = min( Treem[node * 2]  , Treem[node * 2 + 1] );
}

void Query(int node , int le , int ri , int a , int b){
    if(a <= le and b >= ri) {
        ma = max( TreeM[node], ma);
        mi = min(Treem[node],mi);
    return ;
    }
	int mj = (le + ri) / 2;
	if(a <= mj)
		Query(2 * node, le , mj, a , b);
	if(b > mj)
		Query(2 * node + 1, mj + 1 , ri ,a , b);
}
const int Lim = 10000001;
int u =  Lim - 1;
char s[Lim];

void Next () {
    if (++u == Lim)
        std::fread(s, 1, Lim, stdin), u = 0;
}

void Get (int &x) {
 bool semn = false;
    for (; s[u] < '0' || s[u] > '9'; Next());
    if ( s[u-1] == '-')
		semn = true;
    for (x = 0; s[u] >= '0' && s[u] <= '9'; Next())
		   x = x * 10 + s[u] - '0';
		
if( semn == true)
	x*=-1;
}