#include <iostream>
#include <vector>

using namespace std;

const int NMAX = 1e5, NRMAX = 1e5;

int n, q, a[NMAX + 1], segt[4 * NMAX + 1],
    fr[NMAX + 1], last[NMAX + 1],
    ans[NMAX + 1];
vector<pair<int, int> > qs[NMAX + 1];

inline void updateSegt(int poz, int val,
                       int st = 1, int dr = n,
                       int ind = 1) {
    if(st == dr) {
        segt[ind] = val;
        return;
    }
    int mij = (st + dr) / 2;
    if(poz <= mij) updateSegt(poz, val, st, mij, 2 * ind);
    else updateSegt(poz, val, mij + 1, dr, 2 * ind + 1);
    segt[ind] = max(segt[2 * ind], segt[2 * ind + 1]);
}

inline int querySegt(int st, int dr,
                     int sst = 1, int sdr = n,
                     int ind = 1) {
    if(st > dr) return 0;
    if(st == sst && dr == sdr) return segt[ind];

    int smij = (sst + sdr) / 2;
    const int v1 = querySegt(st, min(dr, smij), sst, smij, 2 * ind),
              v2 = querySegt(max(st, smij + 1), dr, smij + 1, sdr, 2 * ind + 1);
    return max(v1, v2);
}

int main()
{
    freopen("pq.in", "r", stdin);
    freopen("pq.out", "w", stdout);
    scanf("%d%d", &n, &q);
    for(int i = 1; i <= n; ++i) {
        scanf("%d", &a[i]);
        last[i] = fr[a[i]];
        fr[a[i]] = i;
    }
    for(int i = 1, st, dr; i <= q; ++i) {
        scanf("%d%d", &st, &dr);
        qs[dr].push_back({st, i});
    }
    for(int dr = 1; dr <= n; ++dr) {
        if(last[dr]) updateSegt(last[dr], dr - last[dr]);
        for(const auto &el : qs[dr]) {
            int st = el.first, i = el.second;
            ans[i] = querySegt(st, dr);
        }
    }
    for(int i = 1; i <= q; ++i)
        printf("%d\n", ans[i] -= !ans[i]);
    return 0;
}