#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 && b < mid+1) {
        ans.SL = LeftNode.SL;
        ans.SM = max(ans.SM, ans.SL);
    }
    else if( b >= mid + 1 && a > mid) {
        ans.SR = RightNode.SR;
        ans.SM = max(ans.SM, ans.SR);
    }
    else if(a <= mid && b >= mid + 1) {
        ans.SL = max(LeftNode.SL, LeftNode.SUM + RightNode.SL);
        ans.SM = max(ans.SM, ans.SL);
        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);
}