#include <bits/stdc++.h>
using namespace std;
const int maxn = 500005;
pair<int, int> a[maxn];
pair<int, pair<int, int> > b[maxn];
pair<int, int> c[maxn];
int t[maxn << 2];
void update(int v, int l, int r, int d, int q) {
  if (l == r) {
    t[v] = q;
    return;
  }
  int m = (l + r) >> 1;
  if (d > m)
    update(v << 1 | 1, m + 1, r, d, q);
  else
    update(v << 1, l, m, d, q);
  int a = t[v << 1];
  int b = t[v << 1 | 1];
  t[v] = a == 0 ? b : b == 0 ? a : a < b ? a : b;
}
int MIN(int v, int l, int r, int L, int R) {
  if (L > R) return 0;
  if (l == L && r == R) return t[v];
  int m = (l + r) >> 1;
  int a = MIN(v << 1, l, m, L, min(R, m));
  int b = MIN(v << 1 | 1, m + 1, r, max(m + 1, L), R);
  return a == 0 ? b : b == 0 ? a : a < b ? a : b;
}
int n, m, q;
void read() {
  scanf("%d %d", &n, &m);
  for (int i = 0; i < n; i++) {
    scanf("%d", &a[i].first);
    a[i].second = i;
  }
  for (int i = 0; i < m; i++) {
    scanf("%d %d", &b[i].first, &b[i].second.first);
    b[i].second.second = i;
  }
}
bool tmp(pair<int, int> a, pair<int, int> b) {
  return a.first != b.first ? a.first < b.first : a.second < b.second;
}
bool tmp1(pair<int, pair<int, int> > a, pair<int, pair<int, int> > b) {
  return a.first != b.first ? a.first < b.first
                            : a.second.first < b.second.first;
}
bool tmp2(pair<int, pair<int, int> > a, pair<int, pair<int, int> > b) {
  return a.second.second < b.second.second;
}
void solve() {
  sort(a, a + n, tmp);
  sort(b, b + m, tmp1);
  for (int i = 0; i < n - 1; i++)
    if (a[i].first == a[i + 1].first)
      a[i] = make_pair(a[i].second, a[i + 1].second);
    else
      a[i] = make_pair(a[i].second, a[i].second);
  a[n - 1] = make_pair(a[n - 1].second, a[n - 1].second);
  int j = m;
  sort(a, a + n, tmp);
  for (int i = n - 1; i >= 0; i--) {
    update(1, 1, n, a[i].second + 1, a[i].second - a[i].first);
    while (j && b[j - 1].first == i + 1) {
      j--;
      int T = MIN(1, 1, n, i + 1, b[j].second.first);
      b[j].first = T ? T : -1;
    }
  }
  sort(b, b + m, tmp2);
}
void write() {
  for (int i = 0; i < m; i++) printf("%d\n", b[i].first);
}
int main() {
  read();
  solve();
  write();
  return 0;
}
