#include <fstream>
#include <iostream>
#include <algorithm>

#define range 100000

using namespace std;

int n,q,i,j,k,l;
int v[range],last[range];

pair<int,int> qr[range];


//de verificat memoria

//definite nod in arbore de intervale
//definitie init prin ampersand, cu parametrii aditionali:
        //parinte si limite
//definitie update
//definitie delete, dupa pointer
//definitie add, dupa pointer spre root, indice, valoare
        //returneaza pointer catre nodul ultim
//definitie get_max, dupa pointer si limita superioara

struct node
{
    int l1,l2,val;
    node *c1,*c2,*p;
}*root,*intv[range];

void init(node *&u,node *p,int l1,int l2)
{
    u=new node;
    u->c1=NULL;
    u->c2=NULL;
    u->l1=l1;
    u->l2=l2;
    u->val=-1;
    u->p=p;
}

void update(node *u)
{
    if(u->c1==NULL&&u->c2==NULL)
    {
        u->val=-1;
    }
    else if(u->c1!=NULL&&u->c2==NULL)
    {
        u->val=u->c1->val;
    }
    else if(u->c1==NULL&&u->c2!=NULL)
    {
        u->val=u->c2->val;
    }
    else
    {
        u->val=max(u->c1->val,u->c2->val);
    }
    if(u->p!=NULL)update(u->p);
}

node* add(node *u,int l, int val)
{
    if(u->l1==u->l2)
    {
        u->val=val;
        update(u->p);
        return u;
    }
    int lp=(u->l1+u->l2)/2;
    if(l<=lp)
    {
        if(u->c1==NULL)init(u->c1,u,u->l1,lp);
        return add(u->c1,l,val);
    }
    else
    {
        if(u->c2==NULL)init(u->c2,u,lp+1,u->l2);
        return add(u->c2,l,val);
    }
}

void del(node *u)
{
    if(u->l1==u->p->l1)
    {
        u->p->c1=NULL;
    }
    else u->p->c2=NULL;
    update(u->p);
    delete u;
}

int get_max(node *u,int lmax)
{
    if(u==NULL)return -1;
    if(u->l2<=lmax)return u->val;
    int lp=(u->l1+u->l2)/2;
    if(lp>=lmax)return get_max(u->c1,lmax);
    return max(get_max(u->c1,lmax),get_max(u->c2,lmax));
}

/*void show(node *u)
{
    if(u->l1==u->l2)cout<<"poz: "<<u->l1+1<<"    val: "<<v[u->l1]<<"   costul: "<<u->val<<'\n';
    else
    {
        if(u->c1!=NULL)show(u->c1);
        if(u->c2!=NULL)show(u->c2);
    }
}*/


int main()
{
    init(root,NULL,0,range);

    fstream f("pq.in",ios::in),g("pq.out",ios::out);
    f>>n>>q;
    for(i=0;i<n;i++)f>>v[i];
    for(i=0;i<range;i++)
    {
        last[i]=-1;
        intv[i]=NULL;
    }
    for(i=n-1;i>=0;i--)
    {
        if(last[v[i]]!=-1)
        {
            intv[i]=add(root,last[v[i]],last[v[i]]-i);
        }
        last[v[i]]=i;
    }


    i=q;
    while(i--)
    {
        f>>qr[i].first;
        qr[i].first--;
        f>>qr[i].second;
        qr[i].second--;
    }
    //vezi cum se sorteaza pair-urile
    sort(qr,qr+q);

    for(i=0,j=0;i<q;i++)
    {
        /*show(root);
        cout<<"\n\n\n\n";*/
        while(j<qr[i].first)
        {
            if(intv[j]!=NULL)del(intv[j]);
            j++;
        }
        g<<get_max(root,qr[i].second)<<'\n';
    }
}