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

/*
提出前に確認!
- setとmultisetを間違えない
*/

/*
ある区間の種類数をカウントしたい
1番目からk番目の種類数をすべてのkについてけいさんできればよさそう
まだ使ってなければその後の区間全体に+1すればいい

これだと重複がうまくいかない
1番目からk番目までに同じ数が二回以上含まれていたら、それは引いてはいけない
重複を計算する配列を別に作る？
あるindexが含まれているかいないかを高速に調べる？

尺取りでできるかと思ったけどできなさそう
1番目からk番目までの種類数をカウントしておく方法だとうまくいかない
必要なのはある区間の重複無しの値の個数
つまり[l, r]の値の個数が欲しい
各nodeの情報はどうすればいいか
値の個数にしてしまうと重複している時に引き過ぎてしまう
単純に重複の個数さえわかれば r - l + 1 - 重複の個数となる
ある区間に含まれている同じ数の個数が知りたい
1からkに含まれている1の個数が知りたい時 -> 現在地から後ろまで+1すればいい
で、区間を引けばいい？
いや、でも1が2個以上ならつむ
*/

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

int INF = 1e9;

struct LazySegmentTree {
private:
    int n;
    //lazyを追加

public:
    vector<long long> node, lazy;
    LazySegmentTree(vector<long long> v) {
        int sz = (int)v.size();
        n = 1; while(n < sz) n *= 2;
        node.resize(2 * n - 1);
        lazy.resize(2 * n - 1, 0);

        for (int i = 0; i < sz; i++) node[i + n - 1] = v[i];
        for (int i = n - 2; i >= 0; i--) node[i] = node[i * 2 + 1] + node[i * 2 + 2];
    }

// k 番目のノードについて遅延評価を行う
void eval(int k, int l, int r) {

    // 遅延配列が空でない場合、自ノード及び子ノードへの
    // 値の伝播が起こる
    if (lazy[k] != 0) {
        node[k] += lazy[k];

        // 最下段かどうかのチェックをしよう
        // 子ノードは親ノードの 1/2 の範囲であるため、
        // 伝播させるときは半分にする（区間に一様に値を足すとすれば、半分に割るというのも納得がいく）
        if (r - l > 1) {
            lazy[2 * k + 1] += lazy[k] / 2;
            lazy[2 * k + 2] += lazy[k] / 2;
        }

        // 伝播が終わったので、自ノードの遅延配列を空にする
        lazy[k] = 0;
    }
}

void add(int a, int b, long long x, int k = 0, int l = 0, int r = - 1) {
    if(r < 0) r = n;

    // k 番目のノードに対して遅延評価を行う
    eval(k, l, r);

    // 範囲外なら何もしない
    if (b <= l || r <= a) return;
    
    // 完全に被覆しているならば、遅延配列に値を入れた後に評価
    if (a <= l && r <= b) {
        lazy[k] += (r - l) * x;
        eval(k, l, r);
    }

    // そうでないならば、子ノードの値を再帰的に計算して、
    // 計算済みの値をもらってくる
    else {
        add(a, b, x, 2 * k + 1, l, (l + r) / 2);
        add(a, b, x, 2 * k + 2, (l + r) / 2, r);
        node[k] = node[2 * k + 1] + node[2 * k + 2];
    }
}

long long getsum(int a, int b, int k = 0, int l = 0, int r = - 1) {
    if (r < 0) r = n;
    if (b <= l || r <= a) return 0;

    // 関数が呼び出されたら評価！
    eval(k, l, r);
    if(a <= l && r <= b) return node[k];
    long long vl = getsum(a, b, 2 * k + 1, l, (l + r) / 2);
    long long vr = getsum(a, b, 2 * k + 2, (l + r) / 2, r);
    return vl + vr;
}

};

int	main(void)
{
	int n, q;
	cin >> n >> q;
	vector<int> c(n);
	for (int i = 0; i < n; i++) cin >> c[i];
	vector<long long> cnt(n + 1, 0);
	LazySegmentTree seg(cnt);
	vector<tuple<int, int, int>> query(q);
	for (int i = 0; i < q; i++)
	{
		int l, r, index;
		cin >> l >> r;
		index = i;
		query[i] = make_tuple(r, l, index);
	}
	sort(query.begin(), query.end());
	vector<pair<int, int>> ans(q);
	vector<int> num_index(n + 1, -1);
	int end = 0;
	for (int i = 0; i < q; i++)
	{
		int l, r, index;
		tie(r, l, index) = query[i];
		while (end < r)
		{
			if (num_index[c[end]] != -1) seg.add(num_index[c[end]] + 1, n + 1, -1);
			seg.add(end + 1, n + 1, 1);
			num_index[c[end]] = end;
			end++;
		}
		int value = seg.getsum(r, r + 1) - seg.getsum(l - 1, l);
		ans[i] = {index, value};
	}
	sort(ans.begin(), ans.end());
	for (int i = 0; i < q; i++) cout << ans[i].second << endl;
	return (0);
}


Measured memory_bytes: 37788