#include <fstream>
#include <deque>
#include <algorithm>
#include <cmath>
using namespace std;

ifstream f("pq.in");
ofstream g("pq.out");

long n,i,j,rmq[100003][25],q,rez[100005],lg,st,last[100005],rez2[100005];


struct interval{
    long x,y,poz;
}C[100005],Q[100005];

bool comp(interval a,interval b)
{
    if (a.y==b.y)
        return a.x<b.x;
    return a.y<b.y;
}
bool comp2(interval a,interval b)
{
    if (a.x==b.x)
        return a.y<b.y;
    return a.x<b.x;
}

void init()
{
    int Maxlg= 0;
    for(; (1 << Maxlg ) <= lg; Maxlg ++);
    Maxlg --;

    for (int i=1;i<=lg;i++)
    {
        rmq[i][0]=C[i].y-C[i].x;
    }
    int i=0;

    for (int k=1;k<=Maxlg;k++)
    {


        for (i=1;i<=lg-(1<<(k-1));i++)
            rmq[i][k] = max(rmq[i][k-1],rmq[i+(1<<(k-1))][k-1]);

    }
}

int ctb(int in,int sf,int nr)
{
    int mij=0;
    while(in<=sf)
    {
        mij=(in+sf)/2;

        if(C[mij].y<nr)
            in=mij+1;
        if(C[mij].y>nr)
            sf=mij-1;
            if (C[mij].y==nr)
                return mij;
    }

    return sf;
}

int query(int st,int dr)
{
    if (dr<st)
    return -1;

    if(st==dr)
        return rmq[st][0];

    int d=dr-st+1;
    int lg = 0;
    for(; (1 << lg ) <= d; lg ++);
    lg --;

    return max(rmq[st][lg],rmq[dr-(1<<lg)+1][lg]);
}

int main()
{
    f>>n>>q;
    for (i=1;i<=n;i++)
    {
        int x;
        f>>x;
        if (last[x]!=0)
        {
            C[++lg].x = last[x];
            C[lg].y = i;
        }
        last[x]=i;
    }
    for (i=1;i<=q;i++)
    {
        f>>Q[i].x>>Q[i].y;
        Q[i].poz=i;
    }
    sort(C+1,C+lg+1,comp);
    sort(Q+1,Q+q+1,comp2);

    init();
    st=1;
    i=1;
    j=1;
    while (st<=lg && j<=q)
    {
        i=st;

        while (C[st].x<Q[j].x && C[st].y<=Q[j].y)
            st++;

        i=ctb(st,lg,Q[j].y);


        rez[j]=query(st,i);
        j++;
    }


    for (i=1;i<=q;i++)
        rez2[Q[i].poz] = rez[i];

    for (i=1;i<=q;i++)
        g<<rez2[i]<<'\n';

    return 0;
}