#include <bits/stdc++.h>
#define nmax 100005
using namespace std;
ifstream in("pq.in");
ofstream out("pq.out");
int sol[nmax], v[nmax], ap[nmax], arb[4*nmax];
int pereche[nmax];
vector<pair<int,int> > itv[nmax];
void upd(int poz, int st, int dr, int pz, int val){
if(st > pz || dr < pz) return;
if(st == dr){
arb[poz] = max(val, arb[poz]);
return;
}
int mid = (st+dr)/2;
upd(poz*2, st, mid, pz, val);
upd(poz*2+1, mid+1, dr, pz, val);
arb[poz] = max(arb[poz*2],arb[poz*2+1]);
}
int sum(int poz, int st, int dr, int a, int b){
if(st > b || dr < a) return 0;
if(st >= a && dr <= b) return arb[poz];
int mid = (st+dr)/2;
int val1 = sum(poz*2, st, mid, a, b);
int val2 = sum(poz*2+1, mid+1, dr, a, b);
return max(val1,val2);
}
int main(){
int n,q;
in >> n >> q;
for(int i=1; i<=n; i++){
in >> v[i];
if(ap[v[i]]){
pereche[i] = ap[v[i]];
}
ap[v[i]] = i;
}
for(int i=0; i<q; i++){
int a,b;
in >> a >> b;
itv[b].push_back({a, i});
}
for(int r = 1; r<=n; r++){
if(pereche[r])
upd(1, 1, n, pereche[r], r-pereche[r]);
for(auto elem: itv[r]){
int l = elem.first;
int qst = elem.second;
sol[qst] = sum(1, 1, n, l, r);
if(sol[qst] == 0){
sol[qst]--;
}
}
}
for(int i=0; i<q; i++){
out << sol[i] << '\n';
}
return 0;
}