#include <bits/stdc++.h>

using namespace std;

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

struct interval
{
    int l,r,ind,sol;
}a[100100];

int compare(interval A,interval B)
{
    if(A.l==B.l)return(A.r<B.r);
    return (A.l>B.l);
}

int compare_again(interval A,interval B)
{
    return (A.ind<B.ind);
}

int n,m,i,j,indice_i,maxi,l,r,last[100100],v[100100],d[2][100100];

int main()
{
    f>>n>>m;
    for(i=1; i<=n; i++)f>>v[i];

    for(i=1; i<=m; i++)f>>a[i].l>>a[i].r,a[i].ind=i;
    sort(a+1,a+m+1,compare);
    indice_i=n;

    int w=1;
    while(w<=m)
    {
        while(indice_i>=a[w].l)
        {
            //cout<<indice_i<<":"<<'\n';
            last[v[indice_i]]=indice_i;
            for(j=indice_i+1; j<=n; j++)
            {
                if(v[indice_i]==v[j])
                {
                    maxi=j-last[v[indice_i]];
                    last[v[indice_i]]=j;
                }
                else maxi=0;

                maxi=max(maxi,d[1][j]);
                maxi=max(maxi,d[0][j-1]);

                d[0][j]=max(maxi,d[0][j]);
                //cout<<j<<" "<<d[0][j]<<"  ";
            }

             for(j=indice_i+1; j<=n; j++)d[1][j]=d[0][j];

            indice_i--;
            //cout<<'\n';
        }

        while(indice_i+1==a[w].l)
        {
            int res=d[1][a[w].r];
            if(res==0)a[w].sol=-1;
            else a[w].sol=res;
            w++;
        }
    }

    sort(a+1,a+m+1,compare_again);
    for(i=1;i<=m;i++)
        g<<a[i].sol<<'\n';

    return 0;
}