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

using namespace std;

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

#define MIN(a , b) (((a) < (b)) ? (a) : (b))
#define MAX(a , b) (((a) < (b)) ? (b) : (a))

int const nmax = 100000;

int v[5 + nmax];
int frec[5 + nmax];

struct Interval{
  int x , y;
  int pos;
  bool operator < (Interval const &a) const{
    return x < a.x;
  }
};
int aint[5 + nmax * 4];

void build(int node , int from , int to){
  if(from < to){
    int mid = (from + to) / 2;

    build(node * 2 , from , mid);
    build(node * 2 + 1 , mid + 1 , to);
    aint[node] = -1;
  } else
    aint[node] = -1;
}
void update(int node , int from ,int to , int x , int val){
  if(from < to){
    int mid = (from + to) / 2;
    if(x <= mid)
      update(node * 2 , from ,mid , x , val);
    else
      update(node * 2 + 1 , mid + 1 , to , x , val);
    aint[node] = MAX(aint[node * 2] , aint[node * 2 + 1]);
  } else
    aint[node] = MAX(aint[node] , val);
}

int queryaint(int node , int from , int to , int x , int y){
  if(from == x && y == to)
    return aint[node];
  else{
    int result = -1;
    int mid = (from + to) / 2;
    if(x <= mid)
      result = MAX(result , queryaint(node * 2 , from , mid , x , MIN(y , mid)));
    if(mid + 1 <= y)
      result = MAX(result , queryaint(node * 2 + 1 , mid + 1 , to , MAX(x , mid + 1) , y));
    return result;
  }
}

Interval query[5 + nmax];
int sol[5 + nmax];

int main()
{
  int n ,q;
  in >> n >> q;
  for(int i = 1 ; i <= n ; i++){
    in >> v[i];
  }
  build(1 , 1 , n);

  for(int i = 1 ; i <= q ; i++){
    in >> query[i].x >> query[i].y;
    query[i].pos = i;
  }

  sort(query + 1 , query + q + 1);
  int computedtill = n + 1;
  for(int i = q ; 1 <= i ; i--){
    while(query[i].x < computedtill){

      computedtill--;
      if(0 < frec[v[computedtill] ] ) {
        update(1 , 1 , n , frec[v[computedtill]] , frec[v[computedtill]] - computedtill);
      }
      frec[v[computedtill]] = computedtill;
    }
    sol[query[i].pos] = queryaint(1 , 1 , n , query[i].x , query[i].y);
  }
  for(int i = 1 ; i <= q ; i++)
    out << sol[i] << '\n';

  return 0;
}