#include <iostream>
#include <fstream>
#include <algorithm>
#include <cstring>
using namespace std;
ifstream fin("pq.in");
ofstream fout("pq.out");
#define MAX 100010

int aint[4 * MAX];

struct sebi{
    int l, r, ind, tip;
} q[2 * MAX];

int ind, val, le, r;
int n, m, dr, a[MAX], last[MAX];

inline bool cmp(sebi a, sebi b)
{
    if(a.r == b.r)
        return a.tip < b.tip;
    return a.r < b.r;
}

void update(int nod, int st, int dr)
{
    if(st == dr)
    {
        aint[nod] = val;
        return;
    }
    int mij = (st + dr) >> 1;
    if(ind <= mij)
        update(2 * nod, st, mij);
    else
        update(2 * nod + 1, mij + 1, dr);
    aint[nod] = max(aint[2 * nod], aint[2 * nod + 1]);
}

int query(int nod, int st, int dr)
{
    if(le <= st && dr <= r)
        return aint[nod];
    int mij = (st + dr) >> 1;
    int val = -1;
    if(le <= mij)
        val = max(val, query(2 * nod, st, mij));
    if(mij + 1 <= r)
        val = max(val, query(2 * nod + 1, mij + 1, dr));
    return val;
}

int main()
{
    int i;
    fin >> n >> m;
    dr = 0;
    for(i = 1 ; i <= n ; i++)
    {
        fin >> a[i];
        q[++dr] = {last[a[i]], i, i, 0};
        last[a[i]] = i;
    }
    for(i = 1 ; i <= m ; i++)
    {
        fin >> le >> r;
        q[++dr] = {le, r, i, 1};
    }
    sort(q + 1, q + dr + 1, cmp);
    memset(aint, -1, sizeof(aint));
    for(i = 1 ; i <= dr ; i++)
    {
        if(q[i].tip == 0)
        {
            ind = q[i].l;
            val = q[i].r - q[i].l;
            if(ind)
                update(1, 1, n);
        }
        else
        {
            le = q[i].l;
            r = q[i].r;
            fout << query(1, 1, n) << "\n";
        }
    }
}