//
//  main.cpp
//

#include <algorithm>
#include <array>
#include <assert.h>
#include <complex>
#include <iomanip>
#include <iostream>
#include <limits>
#include <map>
#include <math.h>
#include <memory>
#include <memory>
#include <queue>
#include <random>
#include <set>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <vector>

using namespace std;

using ll = int64_t;
using ull = uint64_t;

[[maybe_unused]] constexpr ll LL_MAX = numeric_limits<ll>::max();
[[maybe_unused]] constexpr ll LL_MIN = numeric_limits<ll>::min();
[[maybe_unused]] constexpr ull ULL_MAX = numeric_limits<ull>::max();

#define rep(i, a, b) for (ll i = (a); i < (b); i++)
#define rrep(i, a, b) for (ll i = (a)-1; i >= (b); i--)

template <typename T>
void chmin(T& x, T y) {
    x = min(x, y);
}

template <typename T>
void chmax(T& x, T y) {
    x = max(x, y);
}

ll csum(ll x, ll y) {
    if (x > 0 && y > 0 && x > LL_MAX - y) {
        return LL_MAX;
    }
    if (x < 0 && y < 0 && x < LL_MIN - y) {
        return LL_MIN;
    }
    return x + y;
}

template<typename T>
vector<T> make_vec_nd(T init, ll size) {
	return vector<T>(size, init);
}
template<typename T, typename... Args>
auto make_vec_nd(T init, ll size, Args... rest) {
	auto inner = make_vec_nd(init, rest...);
	return vector<decltype(inner)>(size, inner);
}

template<typename Monoid>
struct SegmentTree {
	using Op = function<Monoid(const Monoid& lhs, const Monoid& rhs)>;
	ll width;
	vector<Monoid> node;
	Op op;
	Monoid unit;
 
	SegmentTree(ll N, Op op, Monoid unit)
	: SegmentTree(vector<Monoid>(N, unit), op, unit) {}
	SegmentTree(const vector<Monoid>& elems, Op op, Monoid unit)
	: op(op)
	, unit(unit) {
		width = 1;
		while (width < elems.size()) {
			width *= 2;
		}
		node.resize(2 * width - 1, unit);
		for (size_t i = 0; i < elems.size(); i++) {
			node[i + width - 1] = elems[i];
		}
		for (size_t i = width - 2; i != numeric_limits<size_t>::max(); i--) {
			node[i] = op(node[2 * i + 1], node[2 * i + 2]);
		}
	}
	void update(ll idx, Monoid elem) {
		idx += width - 1;
		node[idx] = elem;
		while (idx >= 1) {
			idx = (idx - 1) / 2;
			node[idx] = op(node[2 * idx + 1], node[2 * idx + 2]);
		}
	}
	Monoid query_core(ll a, ll b, ll root, ll left, ll right) const {
		// assert([left, right) = root以下にある範囲)
		assert(0 <= a && b <= width);
		if (right <= a || b <= left) {
			return unit;
		}
		if (a <= left && right <= b) {
			return node[root];
		}
		ll mid = (left + right) / 2;
		Monoid ans_l = query_core(a, b, 2 * root + 1, left, mid);
		Monoid ans_r = query_core(a, b, 2 * root + 2, mid, right);
		return op(ans_l, ans_r);
	}
	Monoid query(ll a, ll b) const {
		assert(0 <= a && b <= width);
		return query_core(a, b, 0, 0, width);
	}
	Monoid operator[](size_t idx) { return query(idx, idx + 1); }
};

int main() {
	ll N, Q;
	scanf("%lld", &N);
	scanf("%lld", &Q);		
	vector<ll> cols(N);
	vector<vector<ll>> col_to_pos(N);
	ll col_cnt = 0;
	rep(i,0,N) {
		ll col;
		scanf("%lld", &col);
		col--;
		cols[i] = col;
		if (col_to_pos[col].size() == 0) {
			col_cnt++;
		}
		col_to_pos[col].push_back(i);
	}
	struct Range {
		ll id;
		ll left;
		ll right;
	};
	vector<Range> col_ranges;
	col_ranges.reserve(2*N);
	vector<Range> query_ranges;
	query_ranges.reserve(Q);
	rep(col,0,N) {
		vector<ll>& poss = col_to_pos[col];
		if (poss.size() == 0) {
			continue;
		}
		ll start = 0;
		for (ll pos : poss) {
			col_ranges.push_back(Range{-1, start, pos});
			start = pos + 1;
		}
		col_ranges.push_back(Range{-1, start, N});
	}
	rep(q,0,Q) {
		ll l;
		ll r;
		scanf("%lld", &l);
		scanf("%lld", &r);
		l--;
		query_ranges.push_back(Range{q, l, r});
	}
	auto comp_left = [](const Range& lhs, const Range& rhs){
		return lhs.left < rhs.left;
	};
	sort(col_ranges.begin(), col_ranges.end(), comp_left);
	sort(query_ranges.begin(), query_ranges.end(), comp_left);
	vector<ll> ans(Q, col_cnt);
	SegmentTree<ll> rights(N+1, [](ll lhs, ll rhs){ return lhs + rhs; }, 0);
	ll cr_idx = 0;
	ll qr_idx = 0;
	rep(left,0,N) {
		while (cr_idx < col_ranges.size() && col_ranges[cr_idx].left <= left) {
			ll right = col_ranges[cr_idx].right;
			rights.update(right, rights[right] + 1);
			cr_idx++;
		}
		while (qr_idx < Q && query_ranges[qr_idx].left == left) {
			ll id = query_ranges[qr_idx].id;
			ll right = query_ranges[qr_idx].right;
			ans[id] -= rights.query(right, N+1);
			qr_idx++;
		}
	}
	rep(q,0,Q) {
		printf("%d\n", ans[q]);
	}
}



Measured memory_bytes: 85036