#pragma GCC optimize ("O3", "unroll-loops")
//#pragma GCC target ("avx2")
//#pragma comment(linker, "/stack:200000000")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include "bits/stdc++.h"
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define distinct(x) sort(all(x)); x.resize(unique(all(x))-x.begin())
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define CASE(x) int x; cin >> x; while (x--)
#define CASEt(x) int x; cin >> x; for (int tc = 1; tc <= x; ++tc)
using namespace std;
using namespace __gnu_pbds;
namespace {
	const int MOD = 1000000007;
	const int MOD2 = 998244353;
	using ll = long long;
	using ull = unsigned long long;
	using pii = pair<int, int>;
	using pll = pair<ll, ll>;
	template <class T> using ordered_set = tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;
	template <class T> using minheap = priority_queue<T, vector<T>, greater<T>>;
	template <class T> using maxheap = priority_queue<T, vector<T>, less<T>>;
	mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
//	mt19937_64 rng64(chrono::steady_clock::now().time_since_epoch().count());
	template <int MODVALUE>
	struct Modular {
	private:
		long long val;

	public:
		explicit operator long long() const { return val; }

		bool operator == (const Modular& other) { return val == other.val; }
		bool operator != (const Modular& other) { return val != other.val; }
		template<class T> bool operator == (const T& other) { return *this == Modular(other); }
		template<class T> bool operator != (const T& other) { return *this != Modular(other); }
		template<class T> friend bool operator == (const T& other, const Modular& m) { return Modular(other) == m; }
		template<class T> friend bool operator != (const T& other, const Modular& m) { return Modular(other) != m; }

		bool operator <  (const Modular& other) { return val <  other.val; }
		bool operator <= (const Modular& other) { return val <= other.val; }
		bool operator >  (const Modular& other) { return val >  other.val; }
		bool operator >= (const Modular& other) { return val >= other.val; }
		template<class T> bool operator <  (const T& other) { return *this <  Modular(other); }
		template<class T> bool operator <= (const T& other) { return *this <= Modular(other); }
		template<class T> bool operator >  (const T& other) { return *this >  Modular(other); }
		template<class T> bool operator >= (const T& other) { return *this >= Modular(other); }
		template<class T> friend bool operator <  (const T& other, const Modular& m) { return Modular(other) <  m; }
		template<class T> friend bool operator <= (const T& other, const Modular& m) { return Modular(other) <= m; }
		template<class T> friend bool operator >  (const T& other, const Modular& m) { return Modular(other) >  m; }
		template<class T> friend bool operator >= (const T& other, const Modular& m) { return Modular(other) >= m; }

		Modular& operator += (const Modular& other) { val += other.val; val %= MODVALUE; return *this; }
		Modular  operator +  (const Modular& other) { Modular tmp = *this; return tmp += other; }
		template<class T> Modular& operator += (const T& other) { return *this += Modular(other); }
		template<class T> Modular  operator +  (const T& other) { return *this +  Modular(other); }
		template<class T> friend Modular operator += (const T& other, const Modular& m) { return Modular(other) += m; }
		template<class T> friend Modular operator +  (const T& other, const Modular& m) { return Modular(other) +  m; }

		Modular& operator ++()    { return *this += 1; }
		Modular  operator ++(int) { Modular tmp = *this; ++*this; return tmp; }

		Modular  operator -  () const { return Modular(-val); }
		Modular& operator -= (const Modular& other) { val -= other.val; val += MODVALUE; val %= MODVALUE; return *this;}
		Modular  operator -  (const Modular& other) { Modular tmp = *this; return tmp -= other; }
		template<class T> Modular& operator -= (const T& other) { return *this -= Modular(other); }
		template<class T> Modular  operator -  (const T& other) { return *this -  Modular(other); }
		template<class T> friend Modular operator -= (const T& other, const Modular& m) { return Modular(other) -= m; }
		template<class T> friend Modular operator -  (const T& other, const Modular& m) { return Modular(other) -  m; }

		Modular& operator --()    { return *this -= 1; }
		Modular  operator --(int) { Modular tmp = *this; --*this; return tmp; }

		Modular& operator *= (const Modular& other) { val *= other.val; val %= MODVALUE; val += MODVALUE; val %= MODVALUE; return *this; }
		Modular  operator *  (const Modular& other) { Modular tmp = *this; return tmp *= other; }
		template<class T> Modular& operator *= (const T& other) { return *this *= Modular(other); }
		template<class T> Modular  operator *  (const T& other) { return *this *  Modular(other); }
		template<class T> friend Modular operator *= (const T& other, const Modular& m) { return Modular(other) *= m; }
		template<class T> friend Modular operator *  (const T& other, const Modular& m) { return Modular(other) *  m; }

		Modular pow(long long power) const {
			Modular m = *this, ans = 1;
			while (power) {
				if (power & 1) ans *= m;
				m *= m;
				power >>= 1;
			}
			return ans;
		}
		Modular pow(const Modular& other) const { return pow(other.val); }
		Modular inv() const { return pow(MODVALUE-2); }

		Modular& operator /= (const Modular& other) { val *= other.inv().val; val %= MODVALUE; return *this; }
		Modular  operator /  (const Modular& other) { Modular tmp = *this; return tmp /= other; }
		template<class T> Modular& operator /= (const T& other) { return *this /= Modular(other); }
		template<class T> Modular  operator /  (const T& other) { return *this /  Modular(other); }
		template<class T> friend Modular operator /= (const T& other, const Modular& m) { return Modular(other) /= m; }
		template<class T> friend Modular operator /  (const T& other, const Modular& m) { return Modular(other) /  m; }

		friend istream& operator >> (istream& in, Modular& m) { in >> m.val; m.val %= MODVALUE; m.val += MODVALUE; m.val %= MODVALUE; return in; }
		friend ostream& operator << (ostream& out, const Modular& m) { return out << m.val; }

		Modular() : val(0) {}
		Modular(int val) : val((val % MODVALUE + MODVALUE) % MODVALUE) {};
		Modular(long long val) : val((val % MODVALUE + MODVALUE) % MODVALUE) {};
	};
	inline ll pow(ll b, ll p, ll mod) {
		b %= mod;
		ll ans = 1;
		for (; p > 0; p >>= 1) {
			if (p&1) {ans *= b; ans %= mod;}
			b *= b;
			b %= mod;
		}
		return ans;
	}
	inline ll max(ll a, int b) { return (a > b ? a : b); }
	inline ll max(int a, ll b) { return (a > b ? a : b); }
	inline ll min(ll a, int b) { return (a < b ? a : b); }
	inline ll min(int a, ll b) { return (a < b ? a : b); }
	template <class T> inline bool chkmin(T&x, const T& y) { return x > y ? x = y, 1 : 0; }
	template <class T> inline bool chkmax(T&x, const T& y) { return x < y ? x = y, 1 : 0; }
}
namespace IO {
	template<class T> inline void _R(T &x) {cin >> x;}
	template<class T1, class T2> inline void _R(pair<T1,T2> &x) {_R(x.first); _R(x.second);}
	template<class T> inline void _R(vector<T> &x) {for (auto& i : x) _R(i);}
	template<class T> inline void _R(deque<T> &x) {for (auto& i : x) _R(i);}
	inline void R() {}
	template<class T1, class... T2> inline void R(T1 &x, T2 &...y) { _R(x); R(y...);}

	template<class T> inline void _W(const T& x);
	template<class T1, class T2> inline void _W(const pair<T1,T2>& p);
	template<class... T> inline void _W(const vector<T...>& x);
	template<class... T> inline void _W(const deque<T...>& x);
	template<class... T> inline void _W(const forward_list<T...>& x);
	template<class... T> inline void _W(const list<T...>& x);
	template<class... T> inline void _W(const set<T...>& x);
	template<class... T> inline void _W(const multiset<T...>& x);
	template<class... T> inline void _W(const unordered_set<T...>& x);
	template<class... T> inline void _W(const unordered_multiset<T...>& x);
	template<class... T> inline void _W(const map<T...>& x);
	template<class... T> inline void _W(const multimap<T...>& x);
	template<class... T> inline void _W(const unordered_map<T...>& x);
	template<class... T> inline void _W(const unordered_multimap<T...>& x);

	template<class T> inline void _W(const ordered_set<T>& x);

	template<class Container> inline void printContainer(const Container& x) { bool isFirst = 1; for (auto i : x) { if (!isFirst) cout << ' '; isFirst = 0; _W(i); } }

	template<class T> inline void _W(const T& x) {cout << x;}
	template<class T1, class T2> inline void _W(const pair<T1,T2>& p) {_W(p.first); _W(' '); _W(p.second);}
	template<class... T> inline void _W(const vector<T...>& x) { printContainer(x); }
	template<class... T> inline void _W(const deque<T...>& x) { printContainer(x); }
	template<class... T> inline void _W(const forward_list<T...>& x) { printContainer(x); }
	template<class... T> inline void _W(const list<T...>& x) { printContainer(x); }
	template<class... T> inline void _W(const set<T...>& x) { printContainer(x); }
	template<class... T> inline void _W(const multiset<T...>& x) { printContainer(x); }
	template<class... T> inline void _W(const unordered_set<T...>& x) { printContainer(x); }
	template<class... T> inline void _W(const unordered_multiset<T...>& x) { printContainer(x); }
	template<class... T> inline void _W(const map<T...>& x) { printContainer(x); }
	template<class... T> inline void _W(const multimap<T...>& x) { printContainer(x); }
	template<class... T> inline void _W(const unordered_map<T...>& x) { printContainer(x); }
	template<class... T> inline void _W(const unordered_multimap<T...>& x) { printContainer(x); }

	template<class T> inline void _W(const ordered_set<T>& x) { printContainer(x); }

 	inline void W() {cout << '\n';}
	template<class T> inline void W(const T &x) {_W(x); W();}
	template<class T1, class... T2> inline void W(const T1 &x, const T2 &...y) { _W(x); _W(' '); W(y...);}
} using namespace IO;
namespace outputFormat{
	inline string Case(int tc) {return "Case #" + to_string(tc) + ':';}
	inline string YN(bool b) {return b ? "YES" : "NO";}
} using namespace outputFormat;
namespace std {
    template <class T1, class T2> struct hash<pair<T1,T2>> {
    	std::size_t operator()(pair<T1,T2> _) const {
        	return hash<T1>{}(_.first) ^ hash<T2>{}(_.second);
    	}
    };
}
using Mint = Modular<MOD>;


int main() {
	int n,q; R(n,q);
	vector<int> c(n); R(c);
	for (auto& i : c)
		i--;
	
	vector<pair<pii, int>> query(q);
	for (int i = 0; i < q; i++) {
		R(query[i].F);
		query[i].F.F--;
		query[i].F.S--;
		query[i].S = i;
	}
	
	sort(all(query), [&](auto& a, auto& b) {
		const int SZ = 700;
		int Ab = a.F.F / SZ;
		int Bb = b.F.F / SZ;
		if (Ab != Bb)
			return Ab < Bb;
		else
			return a.F.S < b.F.S;
	});
	
	vector<int> ans(q, -1);
	
	int l = 0, r = 0;
	vector<int> cnt(n, 0);
	cnt[c[0]] = 1;
	int tot = 1;
	for (int i = 0; i < q; i++) {
		int ql = query[i].F.F;
		int qr = query[i].F.S;
		
		while (r < qr) {
			r++;
			cnt[c[r]]++;
			if (cnt[c[r]] == 1)
				tot++;
		}
//		W(cnt);
		while (r > qr) {
			cnt[c[r]]--;
			if (cnt[c[r]] == 0)
				tot--;
			r--;
		}
//		W(cnt);
		while (l > ql) {
			l--;
			cnt[c[l]]++;
			if (cnt[c[l]] == 1)
				tot++;
		}
//		W(cnt);
		while (l < ql) {
			cnt[c[l]]--;
			if (cnt[c[l]] == 0)
				tot--;
			l++;
		}
//		W(cnt);
		
		ans[query[i].S] = tot;
	}
	
	for (auto& i : ans)
		W(i);
	
	return 0;
}

static auto _batch_ios = [](){
#ifndef LOCAL
	ios::sync_with_stdio(false);
	cin.tie(0);
#endif
	cout << fixed << setprecision(10);
	return 42;
}();

Measured memory_bytes: 15488