#include <bits/stdc++.h>

using namespace std;

constexpr int MAX_N = 100000;
constexpr int NIL = -1;

int v[MAX_N];

int pointer[MAX_N];
int last[MAX_N];

int answer[MAX_N];

inline int getRight(const long long &A) {
  return (A >> 32LL);
}

inline int getLeft(const long long &A) {
  return A & 4294967295LL;
}

long long query[MAX_N];

struct queryCmp {
  inline bool operator () (const int &A, const int &B) const {
    return query[A] < query[B];
  };
};

class Fenwick {
public:
  void update(const int position, const int key) {
    for (int i = position; i >= 0; i = (i & (i + 1)) - 1)
      if (fen[i] < key)
        fen[i] = key;
  }

  int query(const int position) const {
    int ret = NIL;

    for (int i = position; i < n; i |= (i + 1)) {
      if (fen[i] > ret)
        ret = fen[i];
    }
    return ret;
  }

  Fenwick() {
    n = 0;
    memset(fen, NIL, 4 * MAX_N);
  }

  Fenwick(const int m_size) : n(m_size) {
    memset(fen, NIL, 4 * m_size);
  }

private:
  int fen[MAX_N];
  int n;
};

int main() {
  ifstream fin("pq.in");
  ofstream fout("pq.out");
  fin.tie(0);
  ios_base::sync_with_stdio(0);

  int n, q; fin >> n >> q;

  for (int i = 0; i < n; i += 1)
    fin >> v[i];

  for (int i = 0; i < q; i += 1) {
    int b, e; fin >> b >> e; b -= 1; e -= 1;
    query[i] = ((long long) e << 32LL) | b;
    pointer[i] = i;
  }
  fin.close();

  sort(pointer, pointer + q, queryCmp());

  memset(last, NIL, 4 * MAX_N);

  Fenwick T(n);
  int rightPtr = 0;
  for (int i = 0; i < q; i += 1) {
    const int b = getLeft(query[pointer[i]]),
              e = getRight(query[pointer[i]]);
    while (rightPtr <= e) {
      if (last[v[rightPtr]] != NIL)
        T.update(last[v[rightPtr]], rightPtr - last[v[rightPtr]]);
      last[v[rightPtr]] = rightPtr;
      rightPtr += 1;
    }
    answer[pointer[i]] = T.query(b);
  }

  for (int i = 0; i < q; i += 1) {
    fout << answer[i] << '\n';
  }

  fout.close();

  return 0;
}