#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 {
    long long SL, SR, SM, SUM;
} nodeAux;

int N, M;
long long ans, SUM;
vector<Node> tree;
vector<int> V;

void Read();
void Solve();
void 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);
        ans = SUM = -INF;
        Query(1, 1, N, a, b);
        cout<<ans<<'\n';
    }
}
void Query(int node, int left, int right, int a, int b)
{
    if (a <= left && right <= b) {
        ans = max(ans, max(tree[node].SM, SUM + tree[node].SL) );
        SUM = max(tree[node].SUM + SUM, tree[node].SR);
        return;
    }
    int mid = (left + right) >> 1;
    if(a <= mid)
        Query(nodeL, left, mid, a, b);
    if(b > mid)
        Query(nodeR, mid+1, right, a, b);
}
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);
}