#include <iostream>
#include <algorithm>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <string.h>
#include <vector>
#include <queue>
#include <cmath>
#include <bitset>
#include <complex>
#include <functional>
#include <numeric>
#include <iomanip>

#define SPBR(w, n) std::cout<<(w + 1 == n ? '\n' : ' ');
#define YES cout << "YES" << endl
#define Yes cout << "Yes" << endl
#define NO cout << "NO" << endl
#define No cout << "No" << endl
#define ALL(i) (i).begin(), (i).end()
#define FOR(i, a, n) for(int i=(a);i<(n);++i)
#define RFOR(i, a, n) for(int i=(n)-1;i>=(a);--i)
#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 IN(a, x, b) (a<=x && x<b)
#define OUT(a, x, b) (x<a || b<=x)
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

using ll = long long;
using ull = unsigned long long;
using ld = long double;
const int MOD = 1000000007;
/* const int MOD = 998244353; */
const int INF = 1e18;
const double PI = acos(-1);

using namespace std;
struct INIT { INIT(){
  cin.tie(0); ios::sync_with_stdio(false);
  cout << fixed << setprecision(10);
}}INIT;


template<typename Monoid>
struct SegmentTree {
  using F = function<Monoid(Monoid, Monoid)>;
  int sz;
  vector<Monoid> seg;
  const F f;
  const Monoid M1;
  // SegmentTree<int> seg(N, [](int a, int b) { return min(a, b); }, INT_MAX);
  SegmentTree(int n, const F f, const Monoid &M1) : f(f), M1(M1) {
    sz = 1;
    while(sz < n) sz <<= 1;
    seg.assign(2 * sz, M1);
  }
  // k番目にxを代入
  void set(int k, const Monoid &x) {
    seg[k + sz] = x;
  }
  // 構築
  void build() {
    for(int k = sz - 1; k > 0; k--) {
      seg[k] = f(seg[2 * k + 0], seg[2 * k + 1]);
    }
  }
  // k番目をxに変更
  void update(int k, const Monoid &x) {
    k += sz;
    seg[k] = x;
    while(k >>= 1) {
      seg[k] = f(seg[2 * k + 0], seg[2 * k + 1]);
    }
  }
  // [a, b)に対して結果を返す
  Monoid query(int a, int b) {
    Monoid L = M1, R = M1;
    for(a += sz, b += sz; a < b; a >>= 1, b >>= 1) {
      if(a & 1) L = f(L, seg[a++]);
      if(b & 1) R = f(seg[--b], R);
    }
    return f(L, R);
  }
  // k番目の要素を返す
  Monoid operator[](const int &k) const {
    return seg[k + sz];
  }

  template< typename C >
  int find_subtree(int a, const C &check, Monoid &M, bool type) {
    while(a < sz) {
      Monoid nxt = type ? f(seg[2 * a + type], M) : f(M, seg[2 * a + type]);
      if(check(nxt)) a = 2 * a + type;
      else M = nxt, a = 2 * a + 1 - type;
    }
    return a - sz;
  }
  // [a, x)がcheckを満たす最初の要素位置x
  template<typename C>
  int find_first(int a, const C &check) {
    Monoid L = M1;
    if(a <= 0) {
      if(check(f(L, seg[1]))) return find_subtree(1, check, L, false);
      return -1;
    }
    int b = sz;
    for(a += sz, b += sz; a < b; a >>= 1, b >>= 1) {
      if(a & 1) {
        Monoid nxt = f(L, seg[a]);
        if(check(nxt)) return find_subtree(a, check, L, false);
        L = nxt;
        ++a;
      }
    }
    return -1;
  }
  // [x, b)がcheckを満たす最後の要素位置x
  template<typename C>
  int find_last(int b, const C &check) {
    Monoid R = M1;
    if(b >= sz) {
      if(check(f(seg[1], R))) return find_subtree(1, check, R, true);
      return -1;
    }
    int a = sz;
    for(b += sz; a < b; a >>= 1, b >>= 1) {
      if(b & 1) {
        Monoid nxt = f(seg[--b], R);
        if(check(nxt)) return find_subtree(b, check, R, true);
        R = nxt;
      }
    }
    return -1;
  }
};
  /* SegmentTree<int> seg(N, [](int a, int b) { return min(a, b); }, INF); */
  /* SegmentTree<int> seg(N, [](int a, int b) { return max(a, b); }, -INF); */

signed main() {
  int N, Q;
  cin >> N >> Q;

  vector<int> c(N);
  REP(i, N){
    cin >> c[i];
    c[i]--;
  }

  vector<int> l(Q), r(Q);
  REP(i, Q) cin >> l[i] >> r[i];

  vector<int> o(Q);
  iota(ALL(o), 0);
  sort(ALL(o), [&](int const & ll, int const & rr){
      if(r[ll] == r[rr]) return l[ll] < l[rr];
      return r[ll] < r[rr];
      });


  SegmentTree<int> seg(N, [](int a, int b) { return a+b; }, 0);
  vector<int> ans(Q);
  vector<int> last(N+1, -1);

  int now = 0;
  REP(i, Q){
    int I = o[i];
    while(now < r[I]){
      if(last[c[now]] != -1){
        seg.update(last[c[now]], seg[last[c[now]]]-1);
      }
      last[c[now]] = now+1;

      seg.update(last[c[now]], seg[last[c[now]]]+1);
      now++;
    }
    ans[I] = seg.query(l[I], r[I]+1);
  }

  REP(i, Q){
    cout << ans[i] << "\n";
  }

  return 0;
}


Measured memory_bytes: 19584