#include<bits/stdc++.h>
using namespace std;
const int maxN=(1e5)+5;
int n,q,v[maxN];

vector<int> A[4*maxN+5],aux[4*maxN+5];
int M[maxN],lst[maxN];
const int dim=(1e5);
int pos=0;
char buff[dim+5];

void read(int &nr)
{

    nr=0;
    while(!isdigit(buff[pos]))
    {
        pos++;
        if(pos==dim)
        {
            pos=0;
            fread(buff,1,dim,stdin);
        }
    }

    while(isdigit(buff[pos]))
    {
        nr=nr*10+buff[pos]-'0';
        pos++;
        if(pos==dim)
        {
            pos=0;
            fread(buff,1,dim,stdin);
        }
    }


}
bool cmp(int x,int y)
{
    return lst[x]<lst[y];
}
int nrNodes;

void build(int nod,int st,int dr)
{
    nrNodes=max(nrNodes,nod);
    if(st==dr)
    {
        A[nod].push_back(st);
        return;
    }

    int mid=(st+dr)>>1;

    build(2*nod,st,mid);
    build(2*nod+1,mid+1,dr);

    int i=0;
    int j=0;
    int sz1=(int)A[2*nod].size();
    int sz2=(int)A[2*nod+1].size();

    while(i<sz1 && j<sz2)
    {
        if(cmp(A[2*nod][i],A[2*nod+1][j]))
            A[nod].push_back(A[2*nod][i++]);
        else
            A[nod].push_back(A[2*nod+1][j++]);
    }

    while(i<sz1) A[nod].push_back(A[2*nod][i++]);
    while(j<sz2) A[nod].push_back(A[2*nod+1][j++]);
}
int query(int nod,int st,int dr,int a,int b)
{
    if(a<=st && dr<=b)
    {
        int pos=(int)A[nod].size();
        for(int step=(1<<17);step;step>>=1)
            if(pos>=step && lst[A[nod][pos-step]]>=a) pos-=step;
        if(pos==int(A[nod].size())) return -1;
        return aux[nod][pos];
    }

    int mid=(st+dr)>>1;
    int sol=-1;

    if(a<=mid) sol=max(sol,query(2*nod,st,mid,a,b));
    if(b>mid) sol=max(sol,query(2*nod+1,mid+1,dr,a,b));
    return sol;
}
int main()
{
    freopen("pq.in","r",stdin);
    freopen("pq.out","w",stdout);

    fread(buff,1,dim,stdin);
    read(n);
    read(q);


    for(int i=1;i<=n;i++)
    {
        read(v[i]);
        lst[i]=M[v[i]];
        M[v[i]]=i;
    }


    build(1,1,n);


    for(int i=1;i<=nrNodes;i++)
    {
        if(A[i].empty()) continue;
        int sz=(int)A[i].size();
        aux[i].resize(sz);
        aux[i][sz-1]=A[i][sz-1]-lst[A[i][sz-1]];
        for(int j=sz-2;j>=0;j--)
            aux[i][j]=max(aux[i][j+1],A[i][j]-lst[A[i][j]]);
    }


    while(q--)
    {
        int a,b;
        read(a);
        read(b);
        int sol=query(1,1,n,a,b);
        printf("%d\n",sol);

    }


    return 0;
}