#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) FOR(i,0,n)
#define ALL(v) begin(v),end(v)
#define fi first
#define se second
template<typename A, typename B> inline bool chmax(A &a, B b) { if (a<b) { a=b; return 1; } return 0; }
template<typename A, typename B> inline bool chmin(A &a, B b) { if (a>b) { a=b; return 1; } return 0; }
using ll = long long;
using pii = pair<int, int>;
constexpr ll INF = 1ll<<30;
constexpr ll longINF = 1ll<<60;
constexpr ll MOD = 1000000007;
constexpr bool debug = 0;
//---------------------------------//

template<typename T>
struct SegmentTree {
	using value_type = T;
	using const_reference = const value_type &;
	using F = std::function<value_type(const_reference, const_reference)>;
	using size_type = std::size_t;
	
	SegmentTree(size_type n_, const F & f, const_reference id_elem) : f(f), id_elem(id_elem) {
		n = 1;
		while (n < n_) n <<= 1;
		node.resize(2 * n, id_elem);
	}
	
	size_type size() const noexcept {
		return n;
	}
	
	void set(size_type i, const_reference x) {
		assert(i < size());
		node[i += n] = x;
		while (i > 1) {
			i >>= 1;
			node[i] = f(node[i << 1], node[i << 1 | 1]);
		}
	}
	
	void add(size_type i, const_reference x) {
		assert(i < size());
		i += n;
		node[i] = f(node[i], x);
		while (i > 1) {
			i >>= 1;
			node[i] = f(node[i << 1], node[i << 1 | 1]);
		}
	}
	
	value_type fold(size_type l, size_type r) const {
		assert(l <= size() && r <= size());
		value_type lv = id_elem, rv = id_elem;
		for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
			if (l & 1) lv = f(lv, node[l++]);
			if (r & 1) rv = f(node[r - 1], rv);
		}
		return f(lv, rv);
	}
	
	size_type lower_bound(const_reference x) const {
		if (node[1] < x) return n;
		size_type idx;
		value_type s = id_elem;
		for (idx = 1; idx < n;) {
			value_type nex = f(s, node[idx << 1]);
			if (nex < x) {
				idx = idx << 1 | 1;
				s = nex;
			}
			else idx = idx << 1;
		}
		return idx - n;
	}
	
	size_type upper_bound(const_reference x) const {
		if (node[1] <= x) return n;
		size_type idx;
		value_type s = id_elem;
		for (idx = 1; idx < n;) {
			value_type nex = f(s, node[idx << 1]);
			if (nex <= x) {
				idx = idx << 1 | 1;
				s = nex;
			}
			else idx = idx << 1;
		}
		return idx - n;
	}
	
private:
	size_type n;
	F f;
	value_type id_elem;
	std::vector<value_type> node;
};


int main() {
	int N, Q;
	cin >> N >> Q;
	vector<int> C(N);
	REP(i, N) scanf("%d", &C[i]);
	
	auto compress = [](auto &&v, auto &&cv) -> void {
		for (auto &&u : v) cv.emplace_back(u);
		cv.emplace_back(INF);
		cv.emplace_back(-INF);
		sort(ALL(cv));
		cv.erase(unique(ALL(cv)), cv.end());
		for (auto &&u : v) u = lower_bound(ALL(cv), u) - cv.begin();
	};
	
	vector<int> cx;
	compress(C, cx);
	
	vector<int> L(Q), R(Q);
	REP(i, Q) {
		scanf("%d %d", &L[i], &R[i]);
		--L[i];
	}
	vector<vector<int>> ev(N + 1);
	REP(i, Q) {
		ev[R[i]].emplace_back(i);
	}
	
	vector<int> last(cx.size(), -1);
	SegmentTree<int> seg(N + 1, [](int x, int y) {
		return x + y;
	}, 0);
	
	vector<int> ans(Q);
	REP(i, N) {
		if (last[C[i]] != -1) {
			seg.add(last[C[i]], -1);
		}
		last[C[i]] = i;
		seg.add(last[C[i]], 1);
		for (int j : ev[i + 1]) ans[j] = seg.fold(L[j], N);
	}
	REP(i, Q) printf("%d\n", ans[i]);
	
	return 0;
}


Measured memory_bytes: 40272