#include <fstream>
#include <algorithm>

#define NMax 100010
using namespace std;
ifstream fin("pq.in");
ofstream fout("pq.out");

int ari[NMax * 4];
int n,m,i,x,nr,in,sf;

int f[NMax];

struct Comb{
    int in,sf,i;
    Comb(int a,int b) : in(a), sf(b) {}
    Comb(int a,int b,int i) : in(a), sf(b), i(i) {}
    Comb() : in(0), sf(0), i(0) {}

    bool operator< (const Comb a) const{ return in<=a.in;}
};

Comb C[NMax];
Comb Q[NMax];
void Set(int nod,int in,int sf,int a,int b)
{
    if(in==sf)
    {
        ari[nod]=b;
        return;
    }

    int mij = (in+sf)/2;

    if(a<=mij)
        Set(nod*2,in,mij,a,b);
    else
        Set(nod*2+1,mij+1,sf,a,b);
    ari[nod] = max(ari[nod*2],ari[nod*2+1]);

}

void Set(int a,int b)
{
    Set(1,1,n,a,b);
}

int Get(int nod,int in,int sf,int a,int b)
{

    if(a<=in && sf<=b)
        return ari[nod];


    int mij = (in+sf)/2;

    if(a<=mij)
    {
        if(mij<b)
            return max( Get(nod*2,in,mij,a,b) , Get(nod*2+1,mij+1,sf,a,b));
        return Get(nod*2,in,mij,a,b);
    }

    return Get(nod*2+1,mij+1,sf,a,b);
}

int Get(int a,int b)
{
    return Get(1,1,n,a,b);
}

int main()
{

    fin>>n>>m;

    for(i=1;i<=n;i++)
    {
        fin>>x;
        if(f[x])
        {
            C[++nr] = Comb(f[x],i);
            Set(i,i-f[x]);
        }
        f[x]=i;
    }

    sort(C+1,C+1+nr);

    for(i=1;i<=m;i++)
    {
        fin>>in>>sf;
        Q[i] = Comb(in,sf,i);
    }

    sort(Q+1,Q+1+m);

    int in=1;
    i=1;

    for(i=1;i<=m;i++)
    {
        for(;C[in].in<Q[i].in && in<=nr;in++)
            Set(C[in].sf,0);

        f[Q[i].i] = Get(Q[i].in,Q[i].sf);
        if(f[Q[i].i] == 0)
            f[Q[i].i] = -1;
    }

    for(i=1;i<=m;i++)
        fout<<f[i]<<'\n';

    return 0;
}