#pragma GCC optimize("Ofast,vpt,unroll-loops,shrink-wrap-separate,loop-nest-optimize")
 
#include <bits/stdc++.h>
// #include <tr1/unordered_map>
// #include <ext/rope>
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/trie_policy.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
 
#define IOS ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
#define mt make_tuple
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define mat vector<vector<ll>>
#define mat2 vector<vector<mat>>
#define vi vector<int>
#define vll vector<ll>
#define lll __int128_t
#define psi pair<string, int>
#define pis pair<int, string>
#define pic pair<int, char>
#define pcc pair<char, char>
#define pii pair<int, int>
#define pll pair<ll, ll>
#define piiii pair<pii, pii>
#define mii map<int, int>
#define umii tr1::unordered_map<int, int>
#define iter vector<int>::iterator
#define lb lower_bound
#define ub upper_bound
 

#define fi first
#define se second

/*
#define fi first.first
#define se first.second
#define th second.first
#define fo second.second
*/

/*
#define piii pair<int, pii>
#define fi first
#define se second.fi
#define th second.second
*/
 
/*
#define piii pair<pii, int>
#define fi first.first
#define se first.th
#define th second
*/
 
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
 
using namespace std;
// using namespace __gnu_cxx;
// using namespace __gnu_pbds;
 
typedef long long ll;
typedef long double ld;
// typedef tree<pii, null_type, greater<pii>, rb_tree_tag, tree_order_statistics_node_update> ost;
 
const int nax = 500005, lgax = 24, bit = 64, mod = 1000003, inf = 1000000007;
const ll llax = 9e18;
// const ld pi = 3.14159265358979323846, eps = 1e-7;
 
//mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());

inline int read() {
	char c = getchar_unlocked();
	int t = 0, f = 1;
	while (!isdigit(c) && c != EOF)
		f = (c == '-' ? -1 : 1), c = getchar_unlocked();
	while (isdigit(c) && c != EOF)
		t = t * 10 + c - '0', c = getchar_unlocked();
	return t * f;
}

inline void read(char* s) {
	char c = getchar_unlocked();
	while (isspace(c))
		c = getchar_unlocked();
	while (!isspace(c))
		*s++ = c, c = getchar_unlocked();
	*s = '\0';
}

/*
struct chash {
	static uint64_t splitmix64(uint64_t x)
	{
		x += 0x9e3779b97f4a7c15;
		x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
		x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
		return x ^ (x >> 31);
	}
	size_t operator()(uint64_t x) const
	{
		static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
		return splitmix64(x + FIXED_RANDOM);
	}
};
*/

int lst[nax], res[nax], t[nax];
vector<pii> Q[nax];

void add(int i, int d) {
	for (; i <= nax; i += i & -i)
		t[i] += d;
}

int query(int i) {
	int ans = 0;
	for (; i > 0; i -= i & -i)
		ans += t[i];
	return ans;
}

int main() {
	int n = read(), m = read();
	vi a(n + 1);
	for (int i = 1; i <= n; ++i)
		a[i] = read();
	for (int i = 0; i < m; ++i) {
		int l = read(), r = read();
		Q[r].pb({l, i});
	}
	for (int i = 1; i <= n; ++i) {
		if (lst[a[i]])
			add(lst[a[i]], -1);
		add(lst[a[i]] = i, 1);
		for (pii p : Q[i])
			res[p.se] = query(nax) - query(p.fi - 1);
	}
	for (int i = 0; i < m; ++i)
		printf("%d\n", res[i]);
	return 0;
}


Measured memory_bytes: 33176