#include<stdio.h>
#include<algorithm>
#include<vector>
#include<map>
#define pb push_back
#define mp make_pair
#define lb lower_bound
#define ub upper_bound
#define maxn 100005
#define Lson 2*k
#define Rson 2*k+1
using namespace std;

int n,Q,nr;
int a[maxn],pos[maxn];
pair<int,int> v[maxn];
int vc[maxn];

vector<pair<int,int>> ait[maxn*4];
vector<int> aib[maxn*4];

map<int,int> arb;
map<int,int>::iterator it;

int cnt;

void read()
{
    scanf("%d%d",&n,&Q);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);

    for(int i=n;i;i--)
    {
        it=arb.find(a[i]);
        if( it==arb.end() )
        {
            pos[i]=-1;
            arb.insert(mp(a[i],i));

            continue;
        }

        pos[i]=it->second;
        it->second=i;
    }

    for(int i=1;i<=n;i++) if(pos[i]!=-1)
    {
        nr++;
        v[nr]=mp(i,pos[i]);
    }
}

void update_aib(int ind,int k,int val){
    for(;k<aib[ind].size(); k+=(k^(k-1))&k)
     aib[ind][k]=max(aib[ind][k],val);
}

int query_aib(int ind,int k)
{
    int Max=0;

    for(;k;k-=(k^(k-1))&k) Max=max(Max,aib[ind][k]);
    return Max;
}

bool cmp_merge(const pair<int,int> &A, const pair<int,int> &B){
    return A.second<B.second;
}

void build(int k,int left,int right)
{
    if(left==right)
    {
        ait[k].pb(v[left]);
        aib[k].pb(0);
        aib[k].pb(v[left].second-v[left].first);
        return;
    }

    int mid=(left+right)>>1;
    build(Lson,left,mid);
    build(Rson,mid+1,right);

    ait[k].resize(ait[Lson].size()+ait[Rson].size());
    aib[k].resize(ait[k].size()+1);

    merge(ait[Lson].begin(),ait[Lson].end(),ait[Rson].begin(),ait[Rson].end(),ait[k].begin(),cmp_merge);

    aib[k][0]=0;
    for(unsigned int i=1;i<aib[k].size();i++)
        update_aib(k, i, ait[k][i-1].second-ait[k][i-1].first);
}

bool cmp_b(const int &val,const pair<int,int> &B){
    return val<B.second;
}

int det(int k,int val)
{
    int R = ub(ait[k].begin(),ait[k].end(), val, cmp_b)-ait[k].begin();
    if(R<0 || R>=ait[k].size()) R=ait[k].size();

    if( R<=0 ) return -1;
    return query_aib(k,R);
}

void query(int k,int left,int right,int x,int y,int val)
{
    if(x<=left && right<=y)
    {
        cnt=max(cnt, det(k,val));
        return;
    }

    int mid=(left+right)>>1;
    if(x<=mid) query(Lson,left,mid,x,y,val);
    if(y>mid) query(Rson,mid+1,right,x,y,val);
}

bool cmp_v(const pair<int,int> &A,const pair<int,int> &B){
    return A.first<B.first;
}

void solve()
{
    sort(v+1,v+nr+1,cmp_v);
    for(int i=1;i<=nr;i++) vc[i]=v[i].first;

    int x,y,L,R;
    for(int i=1;i<=Q;i++)
    {
        scanf("%d %d",&x,&y);
        cnt=-1;

        L=lb(vc+1,vc+nr+1,x)-vc;
        R=ub(vc+1,vc+nr+1,y)-vc-1;

        //printf("%d %d\n",L,R);
        if( L>R )
        {
            printf("-1\n");
            continue;
        }

        query(1,1,nr,L,R,y);
        printf("%d\n",cnt);
    }
}

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

    read();
    build(1,1,nr);
    solve();

    fclose(stdin);
    fclose(stdout);
    return 0;
}