#include <iostream>
#include <fstream>
#include <vector>
#define nodeL (node << 1)
#define nodeR ( (node << 1) + 1 )
#define INF ((1 << 29) - 1)
using namespace std;
struct Node {
int SL, SR, SM, SUM;
} nodeAux;
int N, M;
vector<Node> tree;
//Node tree[400000];
vector<int> V;
void Read();
void Solve();
Node Query (int node, int left, int right, int a, int b);
void Update(int node, int left, int right, int pos, int val);
void Build (int node, int left, int right);
int main()
{
Read();
Solve();
return 0;
}
void Solve()
{
int a, b;
Build(1, 1, N);
for(int i=1; i<=M; ++i) {
scanf("%d%d", &a, &b);
cout<<Query(1, 1, N, a, b).SM<<'\n';
}
}
Node Query(int node, int left, int right, int a, int b)
{
if(left == right || (a <= left && right <= b) )
return tree[node];
int mid = (left + right) >> 1;
Node ans, RightNode, LeftNode;
ans.SUM = 0;
ans.SM = ans.SL = ans.SR = -INF;
RightNode.SL = RightNode.SM = RightNode.SR = RightNode.SUM = -INF;
LeftNode.SL = LeftNode.SM = LeftNode.SR = LeftNode.SUM = -INF;
if(a <= mid) {
LeftNode = Query(nodeL, left, mid, a, b);
ans.SUM += LeftNode.SUM;
ans.SM = max(ans.SM, LeftNode.SM);
ans.SL = max(ans.SL, LeftNode.SL);
}
if(b >= mid + 1) {
RightNode = Query(nodeR, mid+1, right, a , b);
ans.SUM += RightNode.SUM;
ans.SM = max(ans.SM, RightNode.SM);
ans.SR = max(ans.SR, RightNode.SR);
}
if(a <= mid) {
ans.SL = max(LeftNode.SL, LeftNode.SUM + RightNode.SL);
ans.SM = max(ans.SM, ans.SL);
}
if( b >= mid + 1) {
ans.SR = max(RightNode.SR, RightNode.SUM + LeftNode.SR);
ans.SM = max(ans.SM, ans.SR);
}
return ans;
}
void Build(int node, int left, int right)
{
if(left == right) {
tree[node].SL = tree[node].SR = tree[node].SM = tree[node].SUM = V[left];
return;
}
int mid = (left + right) >> 1;
Build(nodeL, left, mid);
Build(nodeR, mid+1, right);
tree[node].SUM = tree[nodeL].SUM + tree[nodeR].SUM;
tree[node].SL = max(tree[nodeL].SL, tree[nodeL].SUM + tree[nodeR].SL);
tree[node].SR = max(tree[nodeR].SR, tree[nodeR].SUM + tree[nodeL].SR);
tree[node].SM = max(tree[node].SR, tree[node].SL);
tree[node].SM = max(tree[node].SM, max(tree[nodeL].SM, tree[nodeR].SM) );
tree[node].SM = max(tree[node].SM, tree[nodeL].SR + tree[nodeR].SL);
}
void Read()
{
freopen("sequencequery.in", "rt", stdin);
freopen("sequencequery.out", "wt", stdout);
scanf("%d%d", &N, &M);
V.assign(N+2, 0);
for(int i=1; i<=N; ++i)
scanf("%d", &V[i]);
tree.assign(4*N, nodeAux);
}