#include <bits/stdc++.h>
using namespace std;
const long long inf = 1e9 + 7;
const long long INF = 1e18 + 5;
const long long mxn = 1e6 + 555;
const long long mod = 1e9 + 7;
long long binpow(long long a, long long n) {
  long long res = 1;
  while (n) {
    if (n & 1) res *= a;
    res %= mod;
    a *= a;
    a %= mod;
    n >>= 1;
  }
  return res;
}
long long bl = 316;
long long n, a[mxn], cc[mxn], p[mxn], iii;
long long b[mxn];
long long mx[mxn], mn[mxn];
long long l[mxn], u[mxn];
long long m;
vector<long long> g[mxn];
long long first[mxn];
long long N = 5e5;
long long c[mxn];
long long t[mxn];
void build(int v, int tl, int tr) {
  if (tl == tr) {
    t[v] = a[tl];
    return;
  }
  int md = (tl + tr) >> 1;
  build(v << 1, tl, md);
  build(v << 1 | 1, md + 1, tr);
  t[v] = min(t[v << 1], t[v << 1 | 1]);
}
void upd(int v, int tl, int tr, int x, int y) {
  if (tl == tr) {
    t[v] = y;
    return;
  }
  int tm = (tl + tr) >> 1;
  if (tm >= x)
    upd(v << 1, tl, tm, x, y);
  else
    upd(v << 1 | 1, tm + 1, tr, x, y);
  t[v] = min(t[v << 1], t[v << 1 | 1]);
}
int get(int v, int tl, int tr, int l, int r) {
  if (l > r) return 1e9;
  if (tl == l && tr == r) return t[v];
  int tm = (tr + tl) >> 1;
  return min(get(v << 1, tl, tm, l, min(r, tm)),
             get(v << 1 | 1, tm + 1, tr, max(l, tm + 1), r));
}
vector<int> v[mxn], vv[mxn];
long long d[mxn];
int main() {
  cin.tie(0);
  cout.tie(0);
  ios_base::sync_with_stdio(NULL);
  cin >> n >> m;
  for (int i = 1; i <= n; i++) cin >> a[i];
  map<int, int> mm;
  for (int i = 1; i <= n; i++) {
    l[i] = 1e9;
    if (mm[a[i]] > 0) l[i] = i - mm[a[i]], d[mm[a[i]]] = i;
    upd(1, 1, n, i, l[i]);
    mm[a[i]] = i;
  }
  pair<pair<int, int>, int> p[m + 5];
  for (int i = 1; i <= m; i++)
    cin >> p[i].first.first >> p[i].first.second, p[i].second = i;
  sort(p + 1, p + m + 1);
  int x = 1;
  for (int i = 1; i <= m; i++) {
    while (p[i].first.first > x) upd(1, 1, n, d[x], 1e9), x++;
    b[p[i].second] = get(1, 1, n, 1, p[i].first.second);
    if (b[p[i].second] == 1e9) b[p[i].second] = -1;
  }
  for (int i = 1; i <= m; i++) cout << b[i] << ' ';
  return 0;
}
