#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

#define loopinc(i, a, b, inc) for(int i = a; i < (b); i += inc)
#define loop(i, a, b) for(int i = a; i < (b); i++)
#define rep(i, n) loop(i, 0, n)
#define rrep(i, n) for (int i = n-1; i >= 0; i--)
#define endl "\n"
#define all(c) (c).begin(),(c).end()
#define lloopinc(i, a, b, inc) for(ll i = a; i < (b); i += inc)
#define lloop(i, a, b) for(ll i = a; i < (b); i++)
#define lrep(i, n) lloop(i, 0, n)
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef tuple<int, int, int> tiii;
void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}

template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifndef ONLINE_JUDGE
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif

template<typename T>
struct Fenwick {
        int n;
	std::vector<T> f;
        Fenwick(std::vector<T> a) {
                n = a.size();
                f.resize(n+1);
		std::copy(a.begin(), a.end(), f.begin()+1);
                for (int i = 1; i < n; i++) {
                        int j = i + (i & -i);
                        if (j <= n) f[j] += f[i];
                }
        }
        T query(int i) {
                T acc{};
                for (; i > 0; i -= i & -i) acc += f[i];
                return acc;
        }
        void add(int i, T x) {
                for (i++; i <= n; i += i & -i) f[i] += x;
        }
};

void debf(Fenwick<int> &f) {
	rep(i, f.n) cout << f.query(i+1) - f.query(i) << " ";
	cout << endl;
}

signed main() {
	// freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout);
	std::ios::sync_with_stdio(false);
	cin.tie(0);

	int n, q;
	cin >> n >> q;
	vi c(n); rep(i, n) cin >> c[i];
	rep(i, n) c[i]--;
	vector<pair<pii, int>> qs(q); rep(i, q) cin >> qs[i].first.second >> qs[i].first.first;
	rep(i, q) {
		qs[i].second = i;
		qs[i].first.second--;
	}
	sort(all(qs));
	vi last(n, -1);
	int qi = 0;

	Fenwick<int> f{vi(n)};
	vi ans(q);
	rep(i, n) {
		//debf(f);
		while (qi < q and qs[qi].first.first == i) {
			int r = qs[qi].first.first, l = qs[qi].first.second;
			ans[qs[qi].second] = f.query(r) - f.query(l);
			qi++;
		}
		if (last[c[i]] != -1) f.add(last[c[i]], -1);
		last[c[i]] = i;
		f.add(i, 1);
	}
	int i = n;
	while (qi < q) {
		int r = qs[qi].first.first, l = qs[qi].first.second;
		ans[qs[qi].second] = f.query(r) - f.query(l);
		qi++;
	}
	rep(i, q) cout << ans[i] << endl;
	
	// you should actually read the stuff at the bottom
}
/* stuff you should look for
 * int overflow, array bounds
 * special cases (n=1?)
 * do smth instead of nothing and stay organized
 * WRITE STUFF DOWN
 * also remember to clear global variables on multitest problems
 */
// benq please don't sue me



Measured memory_bytes: 17496