#ifndef TEMPLATE_HPP
#define TEMPLATE_HPP
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < int(n); i++)
#define rrep(i, n) for (int i = int(n) - 1; i >= 0; i--)
#define reps(i, n) for (int i = 1; i <= int(n); i++)
#define rreps(i, n) for (int i = int(n); i >= 1; i--)
#define repc(i, n) for (int i = 0; i <= int(n); i++)
#define rrepc(i, n) for (int i = int(n); i >= 0; i--)
#define repi(i, a, b) for (int i = int(a); i < int(b); i++)
#define repic(i, a, b) for (int i = int(a); i <= int(b); i++)
#define all(a) (a).begin(), (a).end()
#define bit32(x) (1 << (x))
#define bit64(x) (1ll << (x))
#define sz(v) ((int) v.size())
using namespace std;
using i64 = long long;
using f80 = long double;
using vi32 = vector<int>;
using vi64 = vector<i64>;
using vf80 = vector<f80>;
using vstr = vector<string>;
template <typename T> class pqasc : public priority_queue<T, vector<T>, greater<T>> {};
template <typename T> class pqdesc : public priority_queue<T, vector<T>, less<T>> {};
template <typename T> void amax(T &x, T y) { x = max(x, y); }
template <typename T> void amin(T &x, T y) { x = min(x, y); }
template <typename T> T power(T x, i64 n, T e = 1) { T r = e; while (n > 0) { if (n & 1) r *= x; x *= x; n >>= 1; } return r; }
template <typename T> istream& operator>>(istream &is, vector<T> &v) { for (auto &x : v) is >> x; return is; }
template <typename T> ostream& operator<<(ostream &os, vector<T> &v) { rep(i, v.size()) { if (i) os << ' '; os << v[i]; } return os; }
template <typename T, typename U> vector<U> make_vector(T&& n, U&& val) { return vector<U>(forward<T>(n), forward<U>(val)); }
template <typename T, typename... Args> decltype(auto) make_vector(T&& n, Args&&... args) { return vector<decltype(make_vector(forward<Args>(args)...))>(forward<T>(n), make_vector(forward<Args>(args)...)); }
const int INF = 1001001001;
const i64 LINF = 1001001001001001001ll;
const int dx[] = {1, 0, -1, 0, 1, 1, -1, -1};
const int dy[] = {0, 1, 0, -1, 1, -1, 1, -1};
#endif

template <typename T>
struct SegmentTree {
  vector<T> v;
  function<T(T, T)> f;
  T e;
  int n;
  SegmentTree(int size, function<T(T, T)> f, T e) : f(f), e(e) {
    n = 1;
    while (n < size) n <<= 1;
    v.resize(n * 2, e);
  }
  void set(int k, T x) {
    v[k + n] = x;
  }
  void build() {
    for (int i = n - 1; i > 0; i--) {
      v[i] = f(v[i * 2 + 0], v[i * 2 + 1]);
    }
  }
  void update(int k, T x) {
    v[k += n] = x;
    while (k >>= 1) v[k] = f(v[k * 2 + 0], v[k * 2 + 1]);
  }
  T query(int a, int b) {
    T l = e, r = e;
    for (a += n, b += n; a < b; a >>= 1, b >>= 1) {
      if (a & 1) l = f(l, v[a++]);
      if (b & 1) r = f(v[--b], r);
    }
    return f(l, r);
  }
  void reset(int k) {
    update(k, e);
  }
  T operator[](int k) {
    return query(k, k + 1);
  }
};

void solve() {
  int n, q;
  cin >> n >> q;
  vi32 c(n);
  cin >> c;
  rep(i, n) c[i]--;
  SegmentTree<int> st(n, [](int a, int b) { return a + b; }, 0);
  map<int, int> indices;
  vi32 next(n, n);
  rep(i, n) {
    if (indices.count(c[i])) {
      int x = indices[c[i]];
      next[x] = i;
    } else {
      st.set(i, 1);
    }
    indices[c[i]] = i;
  }
  st.build();
  using T = int;
  vector<vector<T>> events(n);
  vi32 l(q), r(q);
  rep(i, q) {
    cin >> l[i] >> r[i];
    l[i]--;
    events[l[i]].emplace_back(i);
  }
  vi32 ans(q);
  rep(i, n) {
    for (auto x : events[i]) {
      ans[x] = st.query(l[x], r[x]);
    }
    st.update(i, 0);
    if (next[i] < n) st.update(next[i], 1);
  }
  rep(i, q) {
    cout << ans[i] << endl;
  }
}

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout << fixed << setprecision(16);
  cerr << fixed << setprecision(16);
  solve();
  return 0;
}

Measured memory_bytes: 61816