/*
Solution Author: Dmitry Sayutin
Date: 29.04.2018
*/

#include <bits/stdc++.h>

using std::cin;
using std::cout;
using std::cerr;

using std::vector;
using std::map;
using std::array;
using std::set;
using std::string;

using std::pair;
using std::make_pair;
using std::tuple;
using std::get;

using std::min;
using std::abs;
using std::max;

using std::unique;
using std::sort;
using std::generate;
using std::reverse;
using std::min_element;
using std::max_element;

#ifdef LOCAL
#define LASSERT(X) assert(X)
#else
#define LASSERT(X) {}
#endif

template <typename T>
T input() {
    T res;
    cin >> res;
    LASSERT(cin);
    return res;
}

template <typename IT>
void input_seq(IT b, IT e) {
    std::generate(b, e, input<typename std::remove_reference<decltype(*b)>::type>);
}

#define SZ(vec)         int((vec).size())
#define ALL(data)       data.begin(),data.end()
#define RALL(data)      data.rbegin(),data.rend()
#define TYPEMAX(type)   std::numeric_limits<type>::max()
#define TYPEMIN(type)   std::numeric_limits<type>::min()

#define pb push_back
#define eb emplace_back

int main() {
    std::iostream::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    
    // code here.
    int n = input<int>();
    int q = input<int>();
    
    vector<int> a(n), compr;

    for (int i = 0; i != n; ++i) {
        a[i] = input<int>();

        compr.push_back(a[i] - 1);
        compr.push_back(a[i]);
        compr.push_back(a[i] + 1);
    }

    std::sort(ALL(compr));
    compr.resize(std::unique(ALL(compr)) - compr.begin());

    for (auto& elem: a)
        elem = std::lower_bound(ALL(compr), elem) - compr.begin();

    vector<int> answers(q, -1);

    const int MO_CONST = 500;
    
    vector<vector<tuple<int, int, int>>> reqs((n + MO_CONST - 1) / MO_CONST); // < r, l, qid >
    
    for (int i = 0; i != q; ++i) {
        int l = input<int>() - 1;
        int r = input<int>() - 1;

        reqs[l / MO_CONST].emplace_back(r, l, i);
    }

    vector<int> go(SZ(compr), -1);
    vector<pair<int, int>> undo;

    int ans = 0;
        
    auto add = [&](int pos) {
        if (go[pos] != -1)
            return;

        undo.emplace_back(pos, -1);
        go[pos] = pos;

        int pl = pos, pr = pos;
        if (pos != 0 and go[pos - 1] != -1)
            pl = go[pos - 1];
        if (pos != SZ(go) - 1 and go[pos + 1] != -1)
            pr = go[pos + 1];

        undo.emplace_back(pl, go[pl]);
        undo.emplace_back(pr, go[pr]);
        go[pl] = pr;
        go[pr] = pl;
        ans = max(ans, pr - pl + 1);
    };

    auto rollback = [&](int tm) {
        while (SZ(undo) > tm) {
            go[undo.back().first] = undo.back().second;
            undo.pop_back();
        }
    };
    
    for (int block = 0; block != SZ(reqs); ++block) {
        std::sort(ALL(reqs[block]));

        rollback(0);
        ans = 0;
        
        int l_end   = min(n - 1, block * MO_CONST + MO_CONST - 1);
        int r_main = l_end + 1;

        int p_request = 0;
        
        for (; p_request != SZ(reqs[block]) and get<0>(reqs[block][p_request]) < r_main; ++p_request) {
            // answer in trivial way.

            int l = get<1>(reqs[block][p_request]);
            int r = get<0>(reqs[block][p_request]);

            for (int i = l; i <= r; ++i)
                add(a[i]);
            
            answers[get<2>(reqs[block][p_request])] = ans;
            ans = 0;
            rollback(0);
        }

        int pr = l_end;
        for (; p_request != SZ(reqs[block]); ++p_request) {            
            while (pr < get<0>(reqs[block][p_request]))
                add(a[++pr]);

            int tm = SZ(undo);
            int ans_old = ans;

            int pl = l_end + 1;
            while (pl > get<1>(reqs[block][p_request]))
                add(a[--pl]);
            
            answers[get<2>(reqs[block][p_request])] = ans;
            rollback(tm);
            ans = ans_old;
        }
    }

    for (auto elem: answers)
        cout << elem << "\n";
        
    return 0;
}