#include <bits/stdc++.h>
using namespace std;

using ll = long long;
#define rep(i, n) for (long long i = 0; i < (n); ++i)
#define repr(i, a, b) for (auto i = (a); i < (b); ++i)
#define itr(x) for (auto&& v : (x))
#define updatemax(t, v) ((t) = std::max((t), (v)))
#define updatemin(t, v) ((t) = std::min((t), (v)))

#include <boost/concept_check.hpp>
#include <functional>
#include <vector>

template <typename T, typename F, typename LazyF = T (*)(const T&, const T&, int)>
class segtree {
  BOOST_CLASS_REQUIRE2(F, std::function<T(T&, T&)>, boost, ConvertibleConcept);
  BOOST_CLASS_REQUIRE2(LazyF, std::function<T(T&, T&, int)>, boost, ConvertibleConcept);

  int n;
  F f;
  T fIdentity;
  LazyF lazyF;
  std::vector<T> data, lazyData;
  std::vector<bool> lazyflag;

  void recalcData(int p, int sectionWidth = 1, bool recurseToTop = false) {
    data[p] = f(data[(p << 1) + 1], data[(p << 1) + 2]);
    if (lazyflag[p]) data[p] = lazyF(data[p], lazyData[p], sectionWidth);
    if (recurseToTop && p > 0) recalcData((p - 1) >> 1, sectionWidth << 1, true);
  }

  void _updateLazy(int begin, int end, const T& value, int p, int pBegin, int pEnd) {
    if (begin <= pBegin && pEnd <= end) {
      addLazyData(p, pEnd - pBegin, value);
    } else if (pBegin < end && begin < pEnd) {
      int pCenter = (pBegin + pEnd) >> 1;
      _updateLazy(begin, end, value, (p << 1) + 1, pBegin, pCenter);
      _updateLazy(begin, end, value, (p << 1) + 2, pCenter, pEnd);
      recalcData(p, pEnd - pBegin, false);
    }
  }

  void addLazyData(int p, int sectionSize, const T& value) {
    data[p] = lazyF(data[p], value, sectionSize);
    lazyData[p] = lazyflag[p] ? lazyF(lazyData[p], value, 1) : value;
    lazyflag[p] = true;
  }

  T _calc(int begin, int end, int p, int pBegin, int pEnd) {
    if (begin <= pBegin && pEnd <= end) {
      return data[p];
    } else if (end <= pBegin || pEnd <= begin) {
      return fIdentity;
    } else {
      int pCenter = (pBegin + pEnd) >> 1;
      if (lazyflag[p]) {
        addLazyData((p << 1) + 1, pCenter - pBegin, lazyData[p]);
        addLazyData((p << 1) + 2, pEnd - pCenter, lazyData[p]);
        lazyflag[p] = false;
      }
      return f(
          _calc(begin, end, (p << 1) + 1, pBegin, pCenter),
          _calc(begin, end, (p << 1) + 2, pCenter, pEnd));
    }
  }

 public:
  segtree(
      int n,
      F f,
      T fIdentity,
      LazyF lazyF = [](const T& baseValue, const T& lazyValue, int sectionSize) { return lazyValue; })
      : f(f), fIdentity(fIdentity), lazyF(lazyF) {
    int logn = 0;
    --n;
    while (n > 0) {
      ++logn;
      n = n >> 1;
    }
    this->n = n = 1 << std::max(logn, 1);
    data.resize(2 * n - 1);
    lazyData.resize(2 * n - 1);
    lazyflag.resize(2 * n - 1);
    for (int i = 0; i < 2 * n - 1; ++i) data[i] = fIdentity;
  }

  void update(int p, const T& value) {
    data[n + p - 1] = value;
    recalcData((n + p - 2) >> 1, 1, true);
  }

  void updateF(int p, const T& value) {
    data[n + p - 1] = f(data[n + p - 1], value);
    recalcData((n + p - 2) >> 1, 1, true);
  }

  void updateLazy(int begin, int end, const T& value) {
    _updateLazy(begin, end, value, 0, 0, n);
  }

  T operator()(int begin, int end) {
    return _calc(begin, end, 0, 0, n);
  }
};

int c[500100], ci[500100];
int main() {
  using Q = tuple<int, int, int>;
  auto qsf = [](const Q& a, const Q& b) { return !(get<2>(a) < get<2>(b)); };
  priority_queue<Q, vector<Q>, decltype(qsf)> qs(qsf);
  int n, q;
  cin >> n >> q;
  rep(i, n) cin >> c[i];
  vector<int> res(q);
  rep(i, q) {
    int l, r;
    cin >> l >> r;
    --l;
    qs.emplace(i, l, r);
  }
  rep(i, 500100) ci[i] = -1;
  segtree t(
      n, [](const int& a, const int& b) { return a + b; }, 0);
  rep(i, n) {
    if (ci[c[i]] >= 0) t.update(ci[c[i]], 0);
    ci[c[i]] = i;
    t.update(i, 1);
    while (!qs.empty() && get<2>(qs.top()) == i + 1) {
      auto [qi, l, r] = qs.top();
      qs.pop();
      res[qi] = t(l, r);
    }
  }
  itr(res) cout << v << endl;
}


Measured memory_bytes: 23804