#include <fstream>
#include <algorithm>
#include <iostream>

using namespace std;

ifstream in("sequencequery.in");
ofstream out("sequencequery.out");

const int MAX_N = 100000;

struct Node {
    long long left;
    long long right;
    long long best;
    int leftSize;
    int rightSize;
    int nSize;
};
Node T[2*MAX_N + 1];

Node join(Node u, Node v) {
    Node w;
    if(u.leftSize == u.nSize && v.left >= 0) {
        w.left = u.left + v.left;
        w.leftSize = u.nSize + v.leftSize;
    }
    else {
        w.left = u.left;
        w.leftSize = u.leftSize;
    }
    if(v.rightSize == v.nSize && u.right >= 0) {
        w.right = v.right + u.right;
        w.rightSize = v.nSize + u.rightSize;
    }
    else {
        w.right = v.right;
        w.rightSize = v.rightSize;
    }
    w.nSize = u.nSize + v.nSize;
    w.best = max(max(u.best, v.best), u.right + v.left);
    return w;
}


void update(int x, int l, int r, int p, int v) {
    if(r - l == 1) {
        T[x] = {v, v, v, 1, 1, 1};
        return;
    }
    if(p < (r+l)/2)
        update(2*x, l, (r+l)/2, p, v);
    else
        update(2*x+1, (r+l)/2, r, p, v);
    T[x] = join(T[2*x], T[2*x+1]);
}

Node query(int x, int l, int r, int i, int j) {
    if(i <= l && r <= j)
        return T[x];
    else if(j <= (r+l)/2)
        return query(2*x, l, (r+l)/2, i, j);
    else if(i >= (r+l)/2)
        return query(2*x+1, (r+l)/2, r, i, j);
    else
        return join(query(2*x, l, (r+l)/2, i, j), query(2*x+1, (r+l)/2, r, i, j));
}

void print(int x, int offset) {
    if(x > 30) return;
    for(int i = 1; i <= offset; i++)
        out << ' ';
    out << T[x].left << ", SIZE " << T[x].leftSize << " | " << T[x].right << ", SIZE " << T[x].rightSize << " | " << T[x].best << ", TOTAL SIZE " << T[x].nSize << "\n";
    print(2*x, offset+4);
    print(2*x+1, offset+4);
}

int main() {
    int n, m, i, x, l, r;

    in >> n >> m;
    for(i = 1; i <= n; i++) {
        in >> x;
        update(1, 1, n+1, i, x);
    }

    for(i = 1; i <= m; i++) {
        in >> l >> r;
        out << query(1, 1, n+1, l, r+1).best << '\n';
    }

    //out << '\n';
    //print(1, 0);



    return 0;
}