#include <iostream>
#include <fstream>
#include <bits/stdc++.h>
using namespace std;
ifstream fin("sequencequery.in");
ofstream fout("sequencequery.out");

const int nmax = 1e5+10;
vector<int> values(nmax,0);
int n,m;
int prefix_ans,suffix_ans,total_ans,ans;

struct Nod{
	long long int max_subarray_sum;
	long long int max_prefix_sum;
	long long int max_suffix_sum;
	long long int total_sum;
};
vector<Nod> aint(nmax*4);
void read_input(){
	fin >> n >> m;
	for(int i = 1; i <=n; i++){
		fin >> values[i];
	}
};

void build_aint(int nod,int index_1,int index_2){
	if(index_1 == index_2){
		aint[nod].max_subarray_sum = 
		aint[nod].max_prefix_sum = 
		aint[nod].max_suffix_sum = 
		aint[nod].total_sum = values[index_1];
	}else{
		int mij = (index_1+index_2)/2;
		build_aint(nod*2,index_1,mij);
		build_aint(nod*2+1,mij+1,index_2);
		
		aint[nod].max_prefix_sum = max(aint[nod*2].max_prefix_sum,
		aint[nod*2].total_sum + aint[nod*2+1].max_prefix_sum);
		
		aint[nod].max_suffix_sum = max(aint[nod*2+1].max_suffix_sum,
		aint[nod*2+1].total_sum + aint[nod*2].max_suffix_sum);
		
		aint[nod].total_sum = aint[nod*2].total_sum + aint[nod*2+1].total_sum;
		
		aint[nod].max_subarray_sum = max({aint[nod*2].max_subarray_sum,
		aint[nod*2+1].max_subarray_sum,aint[nod*2].max_suffix_sum + aint[nod*2+1].max_prefix_sum});
	}
}

Nod query(int nod,int index_1,int index_2,int a,int b){
    if(index_1 > b || index_2 < a){
		return {-9000000000000000000,-9000000000000000000,-9000000000000000000,0};
    }
	if(index_1 >= a && index_2 <= b){
		return aint[nod];
	}else{
		int mij = (index_1+index_2)/2;
		Nod left_node = query(nod*2,index_1,mij,a,b);
		Nod right_node = query(nod*2+1,mij+1,index_2,a,b);
		
		Nod result;
		
		result.max_prefix_sum = max(left_node.max_prefix_sum,
		left_node.total_sum + right_node.max_prefix_sum);
		
		result.max_suffix_sum = max(right_node.max_suffix_sum,
		right_node.total_sum + left_node.max_suffix_sum);
		
		result.total_sum = left_node.total_sum + right_node.total_sum;
		
		result.max_subarray_sum = max({left_node.max_subarray_sum,
		right_node.max_subarray_sum,left_node.max_suffix_sum + right_node.max_prefix_sum});
		
		return result;
	}
}
int main(){
	read_input();
	build_aint(1,1,n);
	for(int i = 1; i <=m; i++){
		int st,dr;
		fin >> st >> dr;
		prefix_ans = suffix_ans = ans = -INT_MAX;
		total_ans = 0;
		Nod ans = query(1,1,n,st,dr);
		fout << ans.max_subarray_sum << '\n';
	};
	return 0;
}