#include <bits/stdc++.h>
#define FastIo() ios_base::sync_with_stdio(false), fin.tie(nullptr),fout.tie(nullptr);
#define ll int64_t
#define pii pair<int,int>
#define pipii pair<int,pair<int,int>>
using namespace std;
ifstream fin("sequencequery.in");
ofstream fout("sequencequery.out");
//
//#define fin cin
//#define fout cout
int n, m, x, y;
const int NMAX = 100001;
ll v[NMAX];
struct tree_node {
ll sum, pref_scmax, sufix_scmax,scmax;
};
vector<tree_node> tree(4 * NMAX);
tree_node update_node(tree_node l_node, tree_node r_node){
tree_node curr_node;
curr_node.sum = l_node.sum + r_node.sum;
curr_node.pref_scmax = max(l_node.pref_scmax, l_node.sum + r_node.pref_scmax);
curr_node.sufix_scmax = max(r_node.sufix_scmax, r_node.sum + l_node.sufix_scmax);
curr_node.scmax = max(l_node.sufix_scmax + r_node.pref_scmax,max(l_node.scmax, r_node.scmax));
return curr_node;
}
void buildTree(int node = 1, int l = 1, int r = n) {
if (l == r) {
tree[node] = { v[l], v[l], v[l], v[l]};
} else {
int m = (l + r) / 2;
buildTree(2 * node, l, m);
buildTree(2 * node + 1, m + 1, r);
tree[node] = update_node(tree[2*node], tree[2*node+1]);
}
}
tree_node query(int node, int l, int r, int queryL, int queryR) {
if (queryL <= l && r <= queryR) {
return tree[node];
} else {
int m = (l + r) / 2;
if (queryR <= m) return query(2 * node, l, m, queryL, queryR);
if (m < queryL) return query(2 * node + 1, m + 1, r, queryL, queryR);
tree_node query0 = query(2 * node, l, m, queryL, queryR);
tree_node query1 = query(2 * node + 1, m + 1, r, queryL, queryR);
tree_node crr;
return {0,0,0,max(query0.sufix_scmax + query1.pref_scmax, max(query0.scmax,query1.scmax))};
}
}
int main() {
fin >> n >> m;
for (int i = 1; i <= n; i++) fin >> v[i];
buildTree();
for(int i=1;i<=m;i++){
fin>>x>>y;
fout<<query(1,1,n,x,y).scmax<<'\n';
}
return 0;
}