#include <bits/stdc++.h>
#define NMAX 10001000
#define x first
#define y second
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

int ARB[400100], VAL,IND,P[100100],IP[100100],N,Q,A[100100],RS[100100];
pair<int , pii > B[100100];

void update(int l,int r,int pos){
    if(l == r){
        ARB[pos] = VAL;
        return;
    }
    
    int m = (l+r)/2;
    
    if(m >= IND) update(l,m,2*pos);
    else update(m+1,r,2*pos+1);
    
    ARB[pos] = max(ARB[2*pos],ARB[2*pos+1]);
}

int query(int l,int r,int pos){
    if(r <= IND) return ARB[pos];
    
    int m = (l+r)/2,a=0,b=0;
    
    a = query(l,m,2*pos);
    if(m < IND) b = query(m+1,r,2*pos+1);
    
    return max(a,b);
}



int main(){
    
	ifstream cin("pq.in");
	ofstream cout("pq.out");

    ios_base::sync_with_stdio(0);
    cin >> N >> Q;
    
    for(int i = 1;i<=N;i++) cin >> A[i];
    for(int i = N;i;i--){
        if(P[A[i]]){
            IND = P[A[i]];
            VAL = P[A[i]]-i; 
            IP[i] = P[A[i]];
            update(1,N,1);
        }
        P[A[i]] = i;
    }
    
    
    for(int i = 0;i<Q;i++){
        cin >> B[i].x >> B[i].y.x;
        B[i].y.y=i;
    }
    
    sort(B,B+Q);
    
    VAL = 0;
    int idx = 1;
    for(int i = 0;i<Q;i++){
        while(idx < B[i].x){
            IND = IP[idx];
            update(1,N,1);
            idx++;
        }
        
        IND = B[i].y.x;
        RS[B[i].y.y] = query(1,N,1);
    
    }
    
    
    for(int i = 0;i<Q;i++) cout << (RS[i] ? RS[i] : -1) << '\n';
    return 0;
}