#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];

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<<19);step;step>>=1)
            if(pos>=step && lst[A[nod][pos-step]]>=a) pos-=step;**/
        int st=0;
        int dr=(int)A[nod].size()-1;
        int sol=dr+1;
        while(st<=dr)
        {
            int mid=(st+dr)>>1;

            if(lst[A[nod][mid]]>=a)
            {

                sol=mid;
                dr=mid-1;
            }
                else st=mid+1;
        }

        if(sol==int(A[nod].size())) return -1;
        return aux[nod][sol];
    }

    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);

    scanf("%d%d",&n,&q);

    for(int i=1;i<=n;i++)
    {
        scanf("%d",&v[i]);
        lst[i]=M[v[i]];
        M[v[i]]=i;
    }


    build(1,1,n);


    for(int i=1;i<=nrNodes;i++)
    {
        int sz=int(A[i].size());
        aux[i].resize(sz+5);
        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;
        scanf("%d%d",&a,&b);
        int sol=query(1,1,n,a,b);
        printf("%d\n",sol);

    }


    return 0;
}