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

using ll = long long;
using ld  = long double;
using pll = pair<ll, ll>;
using pld = pair<ld, ld>;
const int INF=1e9+7;
const ll LINF=9223372036854775807;
const ll MOD=1e9+7;
const ld PI=acos(-1);
const ld EPS = 1e-10; //微調整用（EPSより小さいと0と判定など）

int ii() { int x; if (scanf("%d", &x)==1) return x; else return 0; }
long long il() { long long x; if (scanf("%lld", &x)==1) return x; else return 0; }
string is() { string x; cin >> x; return x; }
char ic() { char x; cin >> x; return x; }
void oi(int x) { printf("%d ", x); }
void ol(long long x) { printf("%lld ", x); }
void od_nosp(double x) { printf("%.15f", x); } // 古い問題用
void od(double x) { printf("%.15f ", x); }
// long doubleで受け取り、fをLfなどに変えて出力すると、変な数値が出る
// それをなんとかするには独自の出力を作らなければならなそう
void os(const string &s) { printf("%s ", s.c_str()); }
void oc(const char &c) { printf("%c ", c); }
#define o_map(v){cerr << #v << endl; for(const auto& xxx: v){cout << xxx.first << " " << xxx.second << "\n";}} //動作未確認
void br() { putchar('\n'); }

// #define gcd __gcd //llは受け取らない C++17~のgcdと違うので注意
// int lcm(int a, int b){return a / gcd(a, b) * b;}
#define begin_end(a) a.begin(),a.end() //sort(begin_end(vec));
#define REP(i,m,n) for(ll i=(ll)(m) ; i < (ll)(n) ; i++ )
#define DREP(i,m,n) for(ll i=(ll)(m) ; i > (ll)(n) ; i-- )
#define rep(i,n) REP(i,0,n)
#define m_p(a,b) make_pair(a,b)
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
#define GET_POS(c,x) (lower_bound(c.begin(),c.end(),x)-c.begin())
#define p_b push_back
#define SZ(x) ((int)(x).size) //size()がunsignedなのでエラー避けに


// coutによるpairの出力（空白区切り）
template<typename T1, typename T2> ostream& operator<<(ostream& s, const pair<T1, T2>& p) {return s << "(" << p.first << " " << p.second << ")";}
// coutによるvectorの出力（空白区切り）
template<typename T> ostream& operator<<(ostream& s, const vector<T>& v) {
  int len = v.size();
  for (int i = 0; i < len; ++i) {
    s << v[i]; if (i < len - 1) s << " "; //"\t"に変えるとTabで見やすく区切る
  }
  return s;
}
// coutによる多次元vectorの出力（空白区切り）
template<typename T> ostream& operator<<(ostream& s, const vector< vector<T> >& vv) {
  int len = vv.size();
  for (int i = 0; i < len; ++i) {
    s << vv[i] << endl;
  }
  return s;
}

//最大値、最小値の更新。更新したor等しければtrueを返す
template<typename T>
bool chmax(T& a, T b){return (a = max(a, b)) == b;}
template<typename T>
bool chmin(T& a, T b){return (a = min(a, b)) == b;}

//4近傍（上下左右） rep(i, 2) にすると右・下だけに進む
vector<int> dx_4 = {1, 0, -1, 0};
vector<int> dy_4 = {0, 1, 0, -1};

// -------- template end - //


// - library ------------- //

ll N, Q;
vector<ll> cs;

// クエリを入れる配列
// < <r, l>, <クエリ番号, クエリに対する答え> > を入れる
// 最初に r で昇順ソートしたいので、<r, l> の順番で入れる
// 最後に答えを出力するときは、pair同士をswapしてからソートし直せばいい
vector<pair<pair<ll, ll>, pair<ll, ll> > > queries_and_answers;

//Binary Indexed Tree (0-indexed)
//sum(k) : [0, k) の合計 O(logN)
//add(k, x) : 要素kに値xを加算 O(logN)
template< typename T >
struct BinaryIndexedTree {
  vector< T > data;

  BinaryIndexedTree(int sz) {
    data.assign(++sz, 0);
  }

  T sum(int k) {
    T ret = 0;
    k -= 1; // [0, k] --> [0, k)
    for(++k; k > 0; k -= k & -k) ret += data[k];
    return (ret);
  }

  void add(int k, T x) {
    for(++k; k < data.size(); k += k & -k) data[k] += x;
  }
};



// --------- library end - //


int main(){

  cin >> N >> Q;
  rep(i, N){
    // 玉の色は 0-indexed にする
    cs.push_back(il() - 1);
  }
  
  rep(i, Q){
    // 添字も 0-indexed にする
    ll l = il() - 1;
    ll r = il() - 1;

    // < <r, l>, <クエリ番号, 答え> >
    queries_and_answers.push_back(make_pair(make_pair(r, l), make_pair(i, 0)));
  }
  // r で昇順ソート
  sort(queries_and_answers.begin(), queries_and_answers.end());


  // ソート済みのクエリを順番に見ていく
  // r がだんだん右に行くので、1つ右に行くごとに、2つの配列を更新していく

  // 配列1) 各色 について、[0, r] の範囲内で、最も右側に出てきた玉（＝解説PDFでいう「良い玉」） の位置
  //  - これは、「rが固定されたとき、rより左側の玉について『一番右側にある玉』だけ見れば十分」ということを利用している
  // 配列2) 各"位置" について、良い玉が存在する数（実際には、良い玉は1つの位置に1つしかありえないので、「存在するかどうか」とも言える

  // rが右に1つ移動した（rが1増えた）ときの配列の更新は、配列2 -> 配列1 の順序で行う。
  // 配列1の更新 : rが右に1つ移動した（rが1増えた）とき、r'=r+1 とすると、新しい「良い玉」が何色かは cs[r'] で O(1) で分かる
  // 配列2の更新 : また、[0, r] -> [0, r'] に区間が伸びる時の配列2の更新は、配列1を利用することで O(1) でできる。具体的には、配列1[新しい玉の色] で「新しい玉と同じ色の玉が前にどこに出たか」を取り出す。
  //  - それが-1なら、初めて出た色なので、「良い玉が1つ増えた」ということで、単に 配列2[r']++; とする。
  //  - -1でなければ、過去に出た色なので、「以前の良い玉が1つなくなり、新しい良い玉が入る」ということで、配列2[同じ色の玉が前に出た位置]--; 配列2[r']++; とする。

  // 配列2 を BIT(Fenwick Tree) で作ることで、毎回のクエリに O(logN) で答えられる。
  // ※先ほどは「配列2の更新は O(1) でできる」と書いたが、BIT を使ったことで、更新は O(logN) まで遅くなる。


  // 配列1 色ごとの良い玉の位置
  vector<ll> array_1(N, -1);

  // 配列2 位置ごとの良い玉の数。初期値は0となっている
  BinaryIndexedTree<ll> bi_tree(N);

  // 右に動かしていく r の値
  // r := 現在、区間 [0, r] までについての配列を保持していることを示す
  // 最初は配列の値が初期値なので、-1 としておく
  ll r = -1; 
  rep(i, Q){
    ll ql = queries_and_answers[i].first.second;
    ll qr = queries_and_answers[i].first.first;

    // qr == r となるまで、rを右に1つずつ動かしていく
    while (r < qr){
      r++;
      if (array_1[cs[r]]==-1){
        // はじめて出た色なら、位置rに良い玉が1つ増えるだけ
        bi_tree.add(r, 1);
      }
      else{
        // 以前に出たことがある色なら、以前の場所から良い玉がなくなり、位置rに1つ増える
        bi_tree.add(array_1[cs[r]], -1);
        bi_tree.add(r, 1);
      }
      // どちらにせよ、今回出た色は良い玉となるので、配列1を更新
      array_1[cs[r]] = r;
    }

    // qr == r となったので、クエリに答える
    // [ql, qr] にある良い玉の数を答えるには、配列2における[ql, qr]の区間和を答えればよい
    // 今回のライブラリには [0, r) の関数しか無いので、累積和の考えで差し引きして取り出す
    // [ql, qr] = [0, qr+1) - [0, ql)
    queries_and_answers[i].second.second =  bi_tree.sum(qr+1) - bi_tree.sum(ql);
  }

  // 答えを出力する

  // < <r, l>, <クエリ番号, 答え> > から < <クエリ番号, 答え>, <r, l> > へ
  for (auto &query : queries_and_answers){
    swap(query.first, query.second);
  }

  // クエリ番号でソート
  sort(queries_and_answers.begin(), queries_and_answers.end());

  for (auto answer : queries_and_answers){
    cout << answer.first.second << endl;
  }


}

Measured memory_bytes: 31176