#include <bits/stdc++.h>

using namespace std;
ifstream fin("sequencequery.in");
ofstream fout("sequencequery.out");
const int Nmax = 100000 + 5;
const int minl = -(1<< 30);
int n, m, A[4 * Nmax], B[4 * Nmax], C[4 * Nmax], S[4 * Nmax], s, ans;

void update(int nod, int l, int r, int poz, int val)
{
    int mid = l + (r - l)/2;

    if(l == r)
    {
        A[nod] = B[nod] = C[nod] = val;
        S[nod] = val;
        return;
    }

    if(poz  <= mid)update(2 * nod, l, mid, poz, val);
    update(2 * nod + 1, mid + 1, r, poz, val);
    S[nod] = S[2 * nod] + S[2 * nod] + 1;
    A[nod] = max(S[2 * nod] + A[2 * nod + 1], A[2 * nod]);
    B[nod] = max(S[2 * nod + 1] + B[2 * nod], B[2 * nod + 1]);
    C[nod] = max(max(C[2 * nod], C[2 * nod + 1]), A[2 * nod + 1] + B[2 * nod]);
}
void query(int nod, int l, int r, int L, int R)
{
    int mid = l + (r - l) / 2;

    if(l > R || r < L)return;

    if(L <= l && R >= r)
    {
        ans = max(ans, max(s + A[nod], C[nod]));
        s = max(s + S[nod], B[nod]);
        return;
    }
    query(2 * nod, l, mid, L, R);
    query(2 * nod + 1, mid + 1, r, L, R);
}
int main()
{
    fin >> n >> m;
    for(int i = 1, x; i <= n; ++i)
        fin >> x, update(1, 1, n, i, x);

    for(int i = 1, a, b; i <= m; ++i)
    {
        fin >> a >> b;
        s = minl; ans = minl;
        query(1, 1, n, a, b);
        fout << ans << '\n';
    }
    return 0;
}