#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;

#define NMAX 100005

struct pereche {
    int id,
        st,
        dr;
} v[ NMAX ] ;

int last[ NMAX ],
     ext[ NMAX ],
     aib[ NMAX ],
     sol[ NMAX ];

bool cmp ( pereche a, pereche b );
void update ( int poz, int k );
int query ( int poz, int n );
int LSB ( int x );


int main () {

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

    int n, m, i, j, k, s;
    s = 0;

    scanf("%d%d",&n,&m);
    for ( i = 1; i <= n; ++i ) {
        scanf("%d",&k);
        if ( last[ k ] ) ext[ i ] = last[ k ];
        last[ k ] = i;
        aib[ i ] = -1;
    }

    for ( i = 1; i <= m; ++i ) {
        scanf("%d%d",&v[ i ].st,&v[ i ].dr);
        v[ i ].id = i;
    }

    sort ( v + 1, v + 1 + m, cmp );

    j = 0;
    for ( i = 1; i <= m; ++i ) {
        while ( j <= v[ i ].dr ) {
            if ( ext[ j ] ) update( ext[ j ], j - ext[ j ] );
            j++;
        }
        sol[ v[ i ].id ] = query( v[ i ].st, n );
    }

    for ( i = 1; i <= m; ++i ) printf("%d\n",sol[ i ]);

    return 0;

}

bool cmp ( pereche a, pereche b ) { return ( a.dr < b.dr ); }
int LSB ( int x ) { return x & ( -x ); }

void update ( int poz, int k ) {

    int i;
    for ( i = poz; i > 0; i -= LSB( i ) )
        aib[ i ] = max( k, aib[ i ] );

}

int query( int poz, int n ) {

    int i, ans = -1;
    for ( i = poz; i <= n; i += LSB( i ) )
        ans = max( ans, aib[ i ] );

    return ans;
}