#include <cstdio>
using namespace std;

const long long infi=(long long)100000 *(long long)1000000;
const int nmax=100000;
const int k=100;

int n;
long long v[ nmax+1 ],s[ nmax+1 ];
long long min[ nmax / k+1 ],best[ nmax / k + 1 ], max[ nmax / k + 1 ];


void build() {
	int i;
	for (i=1; i<=n; ++i) {
		if ( i % k == 0) {
// 			printf ("%d %d %d\n",min[ i/k -1 ], max[ i/k-1 ],best[ i/k-1 ]);
			best[ i / k ]= -infi;
			min[ i/k ]=s[ i-1 ];
			max[ i/k ]=-infi;
		}
		if ( s[ i ] - min[ i / k ] > best[ i / k ]) best[ i / k ]=s[ i ] - min[ i / k ];
		if ( s[ i ] < min[ i / k ] ) min[ i / k ]=s[ i ];
		if ( s[ i ] > max[ i / k ] ) max[ i / k ]=s[ i ];
	}
}

long long solve(int a,int b) {
	int i;
	long long c_min,sol;
	c_min= s[ a-1 ];
	sol=-infi;
	for (; a % k !=0 && a <= b; ++a) { 
		if (s[ a ] - c_min > sol) sol=s[ a ] - c_min;
		if (s[ a ] < c_min) c_min=s[ a ];
	}
	
	if ( a> b ) return sol;
//  	printf ("Cmin =%d Sol=%d\n",c_min,sol);
	for (i= a/k; i < b/k; ++i) {
// 		printf ("best[ %d ]=%d Max=%d\n",i,best[ i ],max[ i ]);
		if (best[ i ] > sol ) sol=best[ i ];
		if (max[ i ] - c_min > sol) sol=max[ i ]- c_min;
		if (min[ i ] < c_min ) c_min= min[ i ];
	}
// 	printf ("Cmin =%d Sol=%d\n",c_min,sol);
	for (a= b - b % k; a <= b; ++a) {
		if (s[ a ] - c_min > sol) sol=s[ a ] - c_min;
		if (s[ a ] < c_min) c_min= s[ a ];
	}
	return sol;
}

int main() {
	FILE *fin=fopen ("sequencequery.in","r");
	FILE *fout=fopen ("sequencequery.out","w");
	int m,a,b,i;
	fscanf (fin,"%d %d",&n,&m);
	for (i=1; i<=n; ++i) {
		fscanf (fin,"%lld",&v[i]);
		s[ i ]=s[ i-1 ] + v[ i ];
	}
	build();
	for (i=1; i<=m; ++i) {
		fscanf (fin,"%d %d",&a,&b);
		fprintf (fout,"%lld\n",solve(a,b));
	}
	fclose(fout);
	return 0;
}