//#pragma warning(disable:4996)
#include <iostream>
#include <vector>
#include <limits.h>
#include <algorithm>
#include <string>
#include <math.h>
#include <limits.h>
#include <queue>
#include <map>
#include <set>
#include <iomanip>
#include <bitset>
#include <cassert>
#include <random>
#include <functional>
#include <stack>
#include <iomanip>
#include <cassert>
//#include <boost/multiprecision/cpp_int.hpp>
#include <complex>
#include <cstdio>
#include <list>
#include <bitset>
//#include <stdio.h>

//< in.txt > out.txt
using namespace std;
//std::ios::sync_with_stdio(false);
//std::cin.tie(0);
const long long MOD = 10000;/// 1e9 + 7;
const long long INF = 1e9;
typedef long long LL;
typedef long double LD;
//typedef boost::multiprecision::cpp_int bigint;
typedef pair<LL, LL> PLL;
typedef pair<int, int> PI;
typedef pair<LD, LL> pdl;
typedef pair<LD, LD> pdd;
typedef vector<LL> VLL;
typedef vector<VLL> VVLL;
typedef vector<int> VI;
typedef vector<vector<int>> VVI;
typedef unsigned long long ULL;

//TT(T,T):=モノイドの乗算
//require Monoid
template<class T>
class Segtree {
private:
	vector<T> seg;
	LL RN;
	typedef function<T(T, T)> TT;
	TT f;
	T te;
public:
	Segtree(LL N, TT _f, T e) :te(e) {
		RN = 1;
		while (RN < N)RN *= 2;
		seg.resize(2 * RN, te);
		f = _f;
	}
	Segtree(vector<T>& V, TT _f, T e) :te(e) {
		LL N = V.size();
		RN = 1;
		while (RN < N)RN *= 2;
		seg.resize(2 * RN, te);
		f = _f;
		for (LL n = 0; n < N; n++) seg[RN + n] = V[n];
		for (LL k = RN - 1; k >= 1; k--) {
			seg[k] = f(seg[2 * k], seg[2 * k + 1]);
		}
	}
	//set n-th as x(0 index!!!!!)
	void set(LL n, T x) {
		seg[RN + n] = x;
		n = (RN + n) / 2;
		while (n >= 1) {
			seg[n] = f(seg[2 * n], seg[2 * n + 1]);
			n /= 2;
		}
	}
	//change n-th number p to x*p(0 index!!!!!)
	void addl(LL n, T x) {
		seg[RN + n] = f(x, seg[RN + n]);
		n = (RN + n) / 2;
		while (n >= 1) {
			seg[n] = f(seg[2 * n], seg[2 * n + 1]);
			n /= 2;
		}
	}
	//change n-th number p to p*x(0 index!!!!!)
	void addr(LL n, T x) {
		seg[RN + n] = f(seg[RN + n], x);
		n = (RN + n) / 2;
		while (n >= 1) {
			seg[n] = f(seg[2 * n], seg[2 * n + 1]);
			n /= 2;
		}
	}
	//get [l,r] (0 index!!!!!)
	T get(LL l, LL r) {
		T ansl = te, ansr = te;
		r++;
		l += RN;
		r += RN;
		while (l < r) {
			if (l & 1) {
				ansl = f(ansl, seg[l]);
				l++;
			}
			if (r & 1) {
				r--;
				ansr = f(seg[r], ansr);
			}
			l >>= 1;
			r >>= 1;
		}
		return f(ansl, ansr);
	}
	//get n-th number(0 index!!!!!)
	T get(LL n) {
		return seg[RN + n];
	}
	T operator[](LL n) {
		return seg[RN + n];
	}
};

struct query {
	int a, b;
	int n;
	query(int _a,int _b,int _n):a(_a),b(_b),n(_n){}
};

int main() {
	std::cin.tie(0);
	std::ios::sync_with_stdio(false);
	int N, Q;
	cin >> N >> Q;
	VI C(N);
	for (int n = 0; n < N; n++) {
		cin >> C[n];
	}
	priority_queue<PI, vector<PI>, function<bool(PI, PI)>> q(
		[](PI a, PI b) {
		return b.second < a.second;
	}
	);
	{
		VI prev(5e5 + 1,-1);
		prev[C[0]] = 0;
		for (int n = 1; n < N; n++) {
			if (prev[C[n]] != -1) {
				q.push(PI(prev[C[n]], n));
			}
			prev[C[n]] = n;
		}
	}
	Segtree<int> seg(N, [](int a, int b) {return a + b; }, 0);
	vector<query> querys;
	for (int q = 0; q < Q; q++) {
		query que(0,0,0);
		cin >> que.a >> que.b;
		que.a--;
		que.b--;
		que.n = q;
		querys.push_back(que);
	}
	sort(querys.begin(), querys.end(), [](query a, query b) {
		return a.b < b.b;
	});
	VI ans(Q);
	for (int t = 0; t < Q; t++) {
		int r = querys[t].b;
		while (!q.empty()) {
			if (q.top().second <= r) {
				seg.set(q.top().first, 1);
				q.pop();
			}
			else break;
		}
		int l = querys[t].a;
		ans[querys[t].n] = (r-l+1)-seg.get(l, r);
	}
	for (int q = 0; q < Q; q++) {
		cout << ans[q] << "\n";
	}
	return 0;
}


Measured memory_bytes: 21824