#include<fstream>
#define ll long long
const int maxn = 100005;
const ll INF = 2000000000000000LL;
using namespace std;

ifstream fin("sequencequery.in");
ofstream fout("sequencequery.out");

struct arbint{
	int max , st , dr , s;
} v[maxn * 5];

ll i , j , n , m , a , x , y , ans , val;

ll maxll ( ll a , ll b ) {
	if ( a > b ) 
		return a;
	return b;
}

void update (int nod , int lf , int rt ) {
	
	if( lf == rt ) {
		v[nod].st = v[nod].dr = v[nod].s = v[nod].max = a;
		return;
	}
	
	int mid = (lf + rt) >> 1;
	
	if( i <= mid ) 
		update(2 * nod , lf , mid );
	else
		update(2 * nod + 1, mid + 1, rt);
	
	v[nod].max = max(v[2 * nod].dr + v[2 * nod + 1].st ,max(v[2 * nod].max , v[2 * nod + 1].max));
	v[nod].s = v[2 * nod].s + v[2 * nod + 1].s;
	v[nod].st = max ( v[2 * nod].st , v[2 * nod].s + v[2 * nod + 1].st );
	v[nod].dr = max ( v[2 * nod + 1].dr , v[2 * nod + 1].s + v[2 * nod].dr);	
	
}

void query (int nod , int lf , int rt ) {
	
	if ( x <= lf && rt <= y ) {
		ll ret = v[nod].max;
		
		ret = maxll ( ret , val + v[nod].st );
		val = maxll ( val + v[nod].s , v[nod].dr );
		ans = maxll ( ans , ret );
	
		return;
	}
	
	int mid = (lf + rt) >> 1;
	
	if ( x <= mid )
		query( 2 * nod , lf , mid );
	if ( y > mid ) 
		query( 2 * nod + 1, mid + 1, rt);
	
}
int main()
{
	freopen("sequencequery.in","r",stdin);
	freopen("sequencequery.out","w",stdout);
	
	fin >> n >> m;
	
	for( i = 1; i <= n ; ++i  ) {
		fin >> a;
		update(1 , 1 , n);
	}
	
	for( i = 1 ; i <= m ;++i ) {
		fin >> x >> y;
		ans = -INF;
		val = 0;
		query(1 , 1, n);
		fout << ans << "\n";
	}
	
return 0;
}