#include<cstdio>

#include<algorithm>

#include<iostream>

#include<cstring>

#include<cmath>

#include<cctype>

#include<set>

#include<queue>

#include<vector>

#include<map>

#include<bitset>

using namespace std;

typedef long long LL;

inline int read() {

    int x=,f=;char ch=getchar();for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-;

    for(;isdigit(ch);ch=getchar())x=x*+ch-'';return x*f;

}

const int N = ;

int bel[N], a[N], ans[N], fa[N], dep[N], B, Top, Mx, n;

bool vis[N];

struct Que{ int l, r, id; } ;

struct Node{ int x, d; } sk[N << ]; // N * 2 !!!

bool operator < (const Que &A,const Que &B) { return A.r < B.r; }

vector< Que > q[N];

int solve1(int x,int y) {

    if (x == y) return ;

    vector<int>vec;

    for (int i = x; i <= y; ++i) vec.push_back(a[i]);

    sort(vec.begin(), vec.end());

    int res = , now = ;

    for (int i = ; i < (int)vec.size(); ++i)

        vec[i] == vec[i - ] +  ? now ++ : now = , res = max(res, now); // !!!

    return res;

}

int find(int x) {

    return x == fa[x] ? x : find(fa[x]);

}

void Union(int x,int y) {

    x = find(x), y = find(y);

    if (x == y) return ;

    if (dep[x] < dep[y]) swap(x, y);

    Mx = max(Mx, dep[x] + dep[y]);

    fa[y] = x;

    sk[++Top] = (Node){x, dep[x]};

    sk[++Top] = (Node){y, dep[y]};

    dep[x] += dep[y];

}

void add(int x) {

    vis[x] = ;

    if (vis[x - ]) Union(x - , x);

    if (vis[x + ]) Union(x, x + );

}

void solve(int now,vector<Que> &vec) {

    Top = , Mx = ;

    int pos = min(N, now * B) + , lastpos, lastmx, L = pos, R = pos - ;

    for (int i = ; i <= n; ++i) fa[i] = i, dep[i] = , vis[i] = ;

    for (int i = ; i < (int)vec.size(); ++i) {

        Que v = vec[i];

        while (R < v.r) add(a[++R]);

        lastmx = Mx, lastpos = Top;

        while (L > v.l) add(a[--L]);

        ans[v.id] = Mx;

        Mx= lastmx;

        while (Top > lastpos) fa[sk[Top].x] = sk[Top].x, dep[sk[Top].x] = sk[Top].d, Top --;

        while (L < pos) vis[a[L ++]] = ;

    }

}

int main() {

    n = read();int m = read(); B = sqrt(n);

    for (int i = ; i <= n; ++i) a[i] = read(), bel[i] = (i - ) / B + ;

    for (int i = ; i <= m; ++i) {

        int x = read(), y = read();

        if (bel[x] == bel[y]) ans[i] = solve1(x, y);

        else q[bel[x]].push_back((Que){x, y, i});

    }

    for (int i = ; i <= bel[n]; ++i) sort(q[i].begin(), q[i].end()), solve(i, q[i]);

    for (int i = ; i <= m; ++i) printf("%d\n", ans[i]);

    return ;

}