#include <bits/stdc++.h>
using namespace std;

typedef long long int ll;
#define endl "\n"
#define pll pair<ll, ll>
#define pii pair<int, int>
#define pb push_back
#define vi vector<int>
#define vl vector<ll>
#define vpii vector<pair<int, int>>
#define mems(x, y) memset(x, y, sizeof(x))
#define all(x) (x).begin(), (x).end()
#define forn(i, s, e) for(int i = s; i < (e); ++i)
#define FASTIO                                                                                     \
	ios_base::sync_with_stdio(false);                                                              \
	cin.tie(NULL);
#define FILEIO                                                                                     \
	freopen("./random06", "r", stdin);                                                             \
	freopen("./output.txt", "w", stdout);
#define debug(...) fprintf(stderr, __VA_ARGS__), fflush(stderr)
#define time__(d)                                                                                  \
	for(auto blockTime = make_pair(chrono::high_resolution_clock::now(), true); blockTime.second;  \
		debug("%s : %lld ms\n ",                                                                   \
			  d,                                                                                   \
			  chrono::duration_cast<chrono::milliseconds>(chrono::high_resolution_clock::now() -   \
														  blockTime.first)                         \
				  .count()),                                                                       \
			 blockTime.second = false)

template <class T>
T ABS(const T& x) {
	return x > 0 ? x : -x;
}
ll gcd(ll n1, ll n2) { return n2 == 0 ? ABS(n1) : gcd(n2, n1 % n2); }
ll lcm(ll n1, ll n2) { return n1 == 0 && n2 == 0 ? 0 : ABS(n1 * n2) / gcd(n1, n2); }
ll ceil2(ll a, ll b) { return (a + b - 1) / b; }

const int N = 500005;
int arr[N], cnt[N];
struct q {
	int l, r, idx;
};

vector<q> qu;
int diff;
int block;
inline bool com(q& a, q& b) {
	if(a.l / block != b.l / block) return a.l / block < b.l / block;
	return a.r < b.r;
}

inline void add(int val) {
	// cerr << val << endl;
	if(cnt[val] == 0) ++diff;
	cnt[val]++;
}
inline void remove(int val) {
	// cerr << val << endl;
	if(cnt[val] == 1) --diff;
	cnt[val]--;
}

int main() {
	// FASTIO
#ifdef LOCAL
	FILEIO
#endif
	time__("start") {

		int n, k;
		scanf("%d %d", &n, &k);

		forn(i, 1, n + 1) scanf("%d", &arr[i]);

		q tmp;
		for(int i = 0; i < k; ++i) {
			scanf("%d %d", &tmp.l, &tmp.r);
			tmp.idx = i + 1;
			qu.push_back(tmp);
		}

		block = 700;
		sort(qu.begin(), qu.end(), com);

		for(int i = 1; i <= n; ++i) { cnt[arr[i]]++; }
		for(int i = 1; i <= n; ++i) {
			if(cnt[i] != 0) ++diff;
		}

		int ans[k + 1];
		int currL = 1, currR = n;
		for(int i = 0; i < k; ++i) {
			int l = qu[i].l, r = qu[i].r;
			// cerr << l << " " << r << " " << currL << " " << currR << " ";
			while(currL < l) {
				//remove
				remove(arr[currL]);
				++currL;
			}

			while(currL > l) {
				--currL;
				add(arr[currL]);
				//add
			}

			while(currR < r) {
				++currR;
				add(arr[currR]);
				//add
			}

			while(currR > r) {
				//remove
				remove(arr[currR]);
				--currR;
			}
			ans[qu[i].idx] = diff;
			// cerr << diff << endl;
		}
		for(int i = 1; i <= k; ++i) { printf("%d\n", ans[i]); }
	}
	return 0;
}

Measured memory_bytes: 15564