#include <iostream>
#include <vector>
#include <array>
#include <list>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <string>
#include <sstream>
#include <algorithm>
#include <random>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <cmath>
#include <cassert>
#include <climits>
#include <bitset>
#include <functional>
#include <iomanip>
#include <random>

#define FOR_LT(i, beg, end) for (int i = (int)(beg); i < (int)(end); i++)
#define FOR_LE(i, beg, end) for (int i = (int)(beg); i <= (int)(end); i++)
#define FOR_DW(i, beg, end) for (int i = (int)(beg); (int)(end) <= i; i--)
#define REP(n)              for (int repeat_index = 0; repeat_index < (int)n; repeat_index++)

using namespace std;

template<typename T>
class SegTree {
public:
	SegTree(int n, function<T(T,T)> operation, function<T(T,T)> update, T identity = T())
	{
		int ne = 1;
		while (ne < n) {
			ne *= 2;
		}
		this->n_  = n;
		this->ne_ = ne;

		this->data_ = vector<T>(this->ne_ * 2, identity);

		this->operation_ = operation;
		this->update_    = update;
		this->identity_ = identity;
	}

	const T& Val(int i) const
	{
		return this->data_[i + this->ne_ - 1];
	}

	void Update(int i, const T& v)
	{
		int idx          = i + this->ne_ - 1;
		this->data_[idx] = this->update_(this->data_[idx], v);

		while (idx != 0) {
			idx      = (idx - 1) / 2;
			int lidx = idx * 2 + 1;
			int ridx = idx * 2 + 2;
			this->data_[idx] = this->operation_(this->data_[lidx], this->data_[ridx]);
		}
	}

	T QueryOpen(int l, int r) const
	{
		return this->QueryInternal(l, r, 0, this->ne_, 0);
	}

	T QueryClose(int l, int r) const
	{
		return QueryOpen(l, r + 1);
	}

private:
	T QueryInternal(int l, int r, int lc, int rc, int idx) const
	{
		if (l <= lc && rc <= r) {
			return this->data_[idx];
		}
		if (rc <= l || r <= lc) {
			return this->identity_;
		}

		int m = (lc + rc) / 2;

		int lidx = idx * 2 + 1;
		int ridx = idx * 2 + 2;

		return this->operation_(
			this->QueryInternal(l, r, lc, m, lidx),
			this->QueryInternal(l, r, m, rc, ridx)
		);
	}

	size_t           n_;
	size_t           ne_;
	vector<T>        data_;
	function<T(T,T)> operation_;
	function<T(T,T)> update_;
	T                identity_;
};

struct Q {
	int l;
	int r;
	int i;
	int a;
};

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout << fixed << setprecision(20);

	int n, m; cin >> n >> m;
	vector<int> cs(n); for (auto& c : cs) cin >> c;

	vector<Q> qs(m);
	FOR_LT(i, 0, m) {
		cin >> qs[i].l >> qs[i].r;
		qs[i].l--;
		qs[i].r--;
		qs[i].i = i;
	}

	sort(qs.begin(), qs.end(), [](const auto& lhs, const auto& rhs) {
		return lhs.l < rhs.l;
	});

	vector<pair<int, int>> vs;
	vector<int> ps(n + 1, -1);
	FOR_LT(i, 0, n) {
		if (ps[cs[i]] != -1) {
			vs.push_back({ ps[cs[i]], i });
		}
		ps[cs[i]] = i;
	}
	sort(vs.begin(), vs.end(), [](const auto& lhs, const auto& rhs) {
		return lhs.first < rhs.first;
		});

	auto vit = vs.begin();
	auto qit = qs.begin();

	auto operation = [](int lhs, int rhs) { return lhs + rhs; };
	auto update = [](int orig, int v) { return orig + v; };
	SegTree<int> st(n, operation, update);

	for (auto v : vs) {
		st.Update(v.second, 1);
	}

	FOR_LT(i, 0, n) {
		while (vit != vs.end() && vit->first < i) {
			st.Update(vit->second, -1);
			vit++;
		}

		while (qit != qs.end() && qit->l == i) {
			qit->a = qit->r - qit->l + 1 - st.QueryClose(qit->l, qit->r);
			qit++;
		}
	}

	vector<int> ans(m);
	for (auto q : qs) {
		ans[q.i] = q.a;
	}
	for (auto a : ans) {
		cout << a << endl;
	}

	return 0;
}


Measured memory_bytes: 24924