#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
#define Nmax 100010

struct _query {int pos, a, b;};

_query queries[Nmax];
int sol[Nmax], a[Nmax], lastPos[Nmax], max_lg[Nmax], nextEl[Nmax];
int aint[4 * Nmax];

void build_aint(int, int, int);
bool CMP(const _query &q1, const _query &q2)
{
    if(q1.a != q2.a) return q1.a < q2.a;
    return q1.b < q2.b;
}
int get_max(int, int, int, int, int);
void aint_delete(int, int, int, int);

int main()
{
    freopen("pq.in", "r", stdin);
    freopen("pq.out", "w", stdout);

    int i, n, q, lastQ, qPos, maxLg, LG;

    cin >> n >> q;
    for(i = 1; i <= n; ++i) cin >> a[i];
    for(i = 1; i <= q; ++i) {queries[i].pos = i; cin >> queries[i].a >> queries[i].b;}

    for(i = n; i >= 1; --i)
    {
        if(lastPos[a[i]]) {max_lg[lastPos[a[i]]] = lastPos[a[i]] - i; nextEl[i] = lastPos[a[i]];}
        lastPos[a[i]] = i;
    }

    build_aint(1, 1, n);

    sort(queries + 1, queries + q + 1, CMP);

    for(qPos = 1, i = 1; i <= n; ++i)
    {
        for(lastQ = 0, maxLg = 0; qPos <= q && queries[qPos].a == i; ++qPos)
        {
            LG = get_max(1, 1, n, lastQ + 1, queries[qPos].b);

            if(LG > maxLg) maxLg = LG;

            sol[queries[qPos].pos] = maxLg;
        }

        aint_delete(1, 1, n, nextEl[i]);
    }

    for(i = 1; i <= q; ++i)
        if(sol[i]) cout << sol[i] << '\n';
    else cout << -1 << '\n';

    return 0;
}

void build_aint(int node, int l, int r)
{
    if(l == r)
    {
        aint[node] = max_lg[l];
        return;
    }

    int mid = (l + r) / 2;

    build_aint(2 * node, l, mid);
    build_aint(2 * node + 1, mid + 1, r);

    aint[node] = max(aint[2 * node], aint[2 * node + 1]);
}

int get_max(int node, int l, int r, int a, int b)
{
    if(a <= l && r <= b) return aint[node];

    int mid = (l + r) / 2, v1 = 0, v2 = 0;

    if(mid >= a) v1 = get_max(2 * node, l, mid, a, b);
    if(mid + 1 <= b) v2 = get_max(2 * node + 1, mid + 1, r, a, b);

    return max(v1, v2);
}

void aint_delete(int node, int l, int r, int pos)
{
    if(l == r) {aint[node] = 0; return;}

    int mid = (l + r) / 2;

    if(pos <= mid) aint_delete(2 * node, l, mid, pos);
    else aint_delete(2 * node + 1, mid + 1, r, pos);

    aint[node] = max(aint[2 * node], aint[2 * node + 1]);
}