#include <iostream>
#include <vector>
using namespace std;

struct SuccinctBitVector
{
	static const int DIV = 16;
	static const int LB = 32768;
	static const int SB = 16;
	static vector<char> popcount_table;
	static bool popcount_calc_flag;
	int size;
	vector<unsigned short> data;
	vector<int> large_block;
	vector<unsigned short> small_block;
	int num_of_ones, num_of_zeros;

	SuccinctBitVector(int size) : size(size) {
		const int data_size = size / DIV + 1;
		const int large_block_size = size / LB + 1;
		const int small_block_size = size / SB + 1;
		data.assign(data_size, 0);
		large_block.assign(large_block_size, 0);
		small_block.assign(small_block_size, 0);
	}

	void set_bit(int idx, bool bit) {
		const int block = idx / DIV;
		const unsigned int mask = 1u << (idx % DIV);
		if (bit) data[block] |= mask;
		else data[block] &= ~mask;
	}

	void build() {
		if (!popcount_calc_flag) popcount_calc();
		const int L = LB / DIV;
		const int S = SB / DIV;
		int ones = 0;
		for (int i = 0; i < data.size(); i++) {
			if (i % L == 0) large_block[i / L] = ones;
			if (i % S == 0) small_block[i / S] = ones - large_block[i / L];
			ones += popcount_table[data[i]];
		}
		num_of_ones = ones;
		num_of_zeros = size - ones;
	}

	int access(int idx) {
		return (data[idx / DIV] >> (idx % DIV)) & 1u;
	}

	int rank(bool bit, int idx) {
		int res = large_block[idx/LB] + small_block[idx/SB] + popcount_table[data[idx/DIV] & ((1u << (idx%DIV)) - 1)];
		if (!bit) res = idx - res;
		return res;
	}

	int select(bool bit, int k) {
		if (k > (bit ? num_of_ones : num_of_zeros) || k < 0) return -1;
		int ng = -1, ok = size;
		while (ok - ng > 1) {
			int mid = (ok + ng) / 2;
			if (rank(bit, mid) >= k) ok = mid;
			else ng = mid;
		}
		return ok;
	}

	void popcount_calc() {
		for (int i = 0; i < (1 << DIV); i++) {
			popcount_table[i] = popcount32(i);
		}
		popcount_calc_flag = true;
	}

	int popcount32(unsigned int x) {
		x = (x & 0x55555555) + ((x >> 1) & 0x55555555);
		x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
		x = (x & 0x0f0f0f0f) + ((x >> 4) & 0x0f0f0f0f);
		x = (x & 0x00ff00ff) + ((x >> 8) & 0x00ff00ff);
		x = (x & 0x0000ffff) + ((x >> 16) & 0x0000ffff);
		return x;
	}
};
bool SuccinctBitVector::popcount_calc_flag = false;
vector<char> SuccinctBitVector::popcount_table(1<<SuccinctBitVector::DIV);

struct WaveletMatrix
{
	int size;
	unsigned long long sigma;
	int bit_size;
	vector<SuccinctBitVector> bvs;
	vector<int> num_of_zeros;

	template<typename T> WaveletMatrix(const vector<T> &data) : size(data.size()) {
		sigma = 0;
		for (auto e : data) {
			if (e > sigma) sigma = e;
		}
		bit_size = bits(sigma);
		sigma++;

		bvs.reserve(bit_size);
		for (int i = 0; i < bit_size; i++) {
			bvs.emplace_back(size);
		}
		num_of_zeros.resize(bit_size);
		vector<unsigned long long> v(size);
		for (int i = 0; i < size; i++) v[i] = data[i];
		for (int i = 0; i < bit_size; i++) {
			vector<unsigned long long> zeros, ones;
			for (int j = 0; j < size; j++) {
				const unsigned long long c = v[j];
				const int bit = (c >> (bit_size - i - 1)) & 1;
				bvs[i].set_bit(j, bit);
				if (bit == 0) zeros.push_back(c);
				else ones.push_back(c);
			}
			bvs[i].build();
			num_of_zeros[i] = zeros.size();
			zeros.insert(zeros.end(), ones.begin(), ones.end());
			v = move(zeros);
		}
	}

	int rank(unsigned long long c, int s, int e) {
		if (c >= sigma) return 0;
		for (int i = 0; i < bit_size; i++) {
			const int bit = (c >> (bit_size - i - 1)) & 1;
			s = bvs[i].rank(bit, s), e = bvs[i].rank(bit, e);
			if (bit) s += num_of_zeros[i], e += num_of_zeros[i];
		}
		return e - s;
	}

	int rank(unsigned long long c, int e) {
		return rank(c, 0, e);
	}

	int range_freq(unsigned long long x, unsigned long long y, int s, int e) {
		if (x >= y) return 0;
		const auto b = get<1>(rank_all(y, s, e));
		const auto a = get<1>(rank_all(x, s, e));
		return b - a;
	}

	tuple<int, int, int> rank_all(unsigned long long c, int s, int e) {
		if (c >= sigma) return make_tuple(0, e - s, 0);
		if (s >= e) return make_tuple(0, 0, 0);
		int less = 0, more = 0;
		for (int i = 0; i < bit_size; i++) {
			const int bit = (c >> (bit_size - i - 1)) & 1, tmp = e - s;
			s = bvs[i].rank(bit, s), e = bvs[i].rank(bit, e);
			if (bit) {
				less += tmp - (e - s);
				s += num_of_zeros[i], e += num_of_zeros[i];
			} else {
				more += tmp - (e - s);
			}
		}
		return make_tuple(e - s, less, more);
	}

	int bits(unsigned long long x) {
		if (x == 0) return 1;
		int res = 0;
		while (x >> res) {
			res++;
		}
		return res;
	}
};

struct P
{
	int x, y;
	P(int x=0, int y=0) : x(x), y(y) {}
	friend ostream &operator <<(ostream &os, const P &a) {
		return os << '(' << a.x << ',' << a.y << ')';
	}
	bool operator <(const P &r) const {
		if (x == r.x) return y < r.y;
		return x < r.x;
	}
};

int main() {
	int n, Q;
	cin >> n >> Q;
	vector<int> last_idx(n+1, -1);
	vector<P> intervals;
	for (int i = 0; i < n; i++) {
		int c;
		scanf("%d", &c);
		if (last_idx[c] != -1) intervals.emplace_back(last_idx[c], i);
		last_idx[c] = i;
	}
	sort(intervals.begin(), intervals.end());
	int m = intervals.size();
	vector<int> v(m);
	for (int i = 0; i < m; i++) {
		v[i] = intervals[i].y;
	}
	WaveletMatrix wm(v);
	for (int q = 0; q < Q; q++) {
		int l, r;
		scanf("%d%d", &l, &r);
		l--;
		int xl = lower_bound(intervals.begin(), intervals.end(), P(l, -1)) - intervals.begin();
		int xr = lower_bound(intervals.begin(), intervals.end(), P(r, -1)) - intervals.begin();
		int ans = (r - l) - wm.range_freq(l, r, xl, xr);
		printf("%d\n", ans);
	}
	return 0;
}

Measured memory_bytes: 32084