#include <bits/stdc++.h>
#define N 100005

using namespace std;

ifstream fin("pq.in") ;
ofstream fout("pq.out") ;

vector<pair<int,int> > v[N] ;
int dp[N] , arb[4*N] , maxim , t[N] , sol[N] ;

void modific (int nod , int l , int r , int val , int poz )
{
    if ( l == r )
    {
        arb[nod] = val ;
        return ;
    }
    int med = (l+r) / 2 ;
    if ( poz <= med )
        modific(nod*2 , l , med , val , poz) ;
    else
        modific(2*nod+1 , med+1 , r , val , poz ) ;
    arb[nod] = max(arb[nod*2],arb[nod*2+1]) ;
}

void query(int nod , int l , int r , int x , int y )
{
    if ( x <= l && r <= y )
    {
        maxim = max(maxim,arb[nod]) ;
        return ;
    }
    int med = (l+r) / 2 ;
    if ( x <= med )
        query(nod*2,l,med,x,y) ;
    if ( y > med )
        query(nod*2+1,med+1,r,x,y) ;
}

int main()
{
    int n , m , i , x , y , poz , val ;
    fin >> n >> m ;
    val = -1 ;
    for ( i = 1 ; i <= n ; i++ )
    {
        poz = i ;
        fin >> t[i] ;
        modific(1,1,n,val,poz) ;
    }
    for ( i = 1 ; i <= m ; i++ )
    {
        fin >> x >> y ;
        v[y].push_back(make_pair(x,i)) ;
    }
    for ( i = 1 ; i <= n ; i++ )
    {
        if ( dp[t[i]] != 0 )
        {
            poz = dp[t[i]] ;
            val = i - poz ;
            modific(1,1,n,val,poz) ;
        }
        dp[t[i]] = i ;
        for ( auto j : v[i] )
        {
            maxim = -1 ;
            query(1,1,n,j.first,i) ;
            sol[j.second] = maxim ;
        }
    }
    for ( i = 1 ; i <= m ; i++ )
        fout << sol[i] << '\n' ;
}