// #pragma GCC optimize ("O3")
	// #pragma GCC target ("sse4")

	#include <bits/stdc++.h>
	using namespace std;
	const int INF = 1 << 29;
	const int NINF = -1*INF;
	const long long LLINF = 1ll << 60;
	const long long LLNINF = -1*LLINF;

	template <class Ch, class Tr, class Container>
	basic_ostream <Ch, Tr> & operator << (basic_ostream <Ch, Tr> & os, Container const& x) {
	    os << "{ ";
	    for(auto& y : x) os << y << " ";
	    return os << "}";
	}

	template <class X, class Y>
	ostream & operator << (ostream & os, pair <X, Y> const& p) {
		return os << "[ " << p.first << ", " << p.second << "]" ;
	}

	typedef long long ll;
	typedef unsigned long long ull;
	typedef long double ld;
	 
	typedef pair<int, int> pi;
	typedef pair<ll,ll> pll;
	typedef pair<ld,ld> pd;

	typedef vector<int> vi;
	typedef vector<ll> vll;
	typedef vector<double> vd;
	typedef vector<ld> vld;
	typedef vector<pi> vpi;
	typedef vector<pll> vpll;
	typedef vector<vector<int>> vvi;
	typedef vector<vll> vvll;
	typedef vector<vd> vvd;
	typedef vector<vld> vvld;
	 
	#define mp make_pair
	#define pb push_back
	#define pf push_front
	#define all(x) x.begin(), x.end()
	#define revAll(x) x.rbegin(), x.rend()
	#define gcd(a, b) __gcd(a, b)
	#define popcount(x) __builtin_popcount(x)
	#define isize(x) (int)(x.size())
	#define rep(i,n) for(int i = 0; i < n; i++)
	#define rep1(i, n) for(int i = 1; i < n+1; i++)
	#define umap unordered_map

	const ll MOD = 1e9 + 7;

	// points type 0, queries type 1
	struct Event{
		int type, start, end, val;

		Event(int t, int s, int e, int v){
			type = t, start = s, end = e, val = v;
		}

		bool operator<(const Event& other){
			return mp(end, type) < mp(other.end, other.type);
		}

	};

	struct SegTree{
		int n;
		vll T;

		SegTree(int sizen){
			n = sizen;
			T = vll(4*n+10);
		}

		void update_(int i, ll val, int v, int tl, int tr){
			if (tl == tr){
				T[v] = val;
			}else{
				int mid = (tl + tr)/2;
				if (i <= mid){
					update_(i, val, 2*v, tl, mid);
				}else{
					update_(i, val, 2*v+1, mid+1, tr);
				}
				T[v] = T[2*v] + T[2*v+1];
			}
		}

		void update(int i, ll val){
			update_(i, val, 1, 0, n-1);
		}

		ll range_sum_(int l, int r, int v, int tl, int tr){
			if (l > tr or r < tl) return 0;
			if (l <= tl and tr <= r) return T[v];
			int mid = (tl + tr)/2;
			ll L = range_sum_(l, r, 2*v, tl, mid);
			ll R = range_sum_(l, r, 2*v+1, mid+1, tr);
			return L + R;
		}

		ll range_sum(int l, int r){
			return range_sum_(l, r, 1, 0, n-1);
		}

	};

	int main(){
		ios_base::sync_with_stdio(false);cin.tie(0);
		int n, q; cin >> n >> q;
		vector<Event> events = vector<Event>();
		vi ans = vi(q);
		rep(i, n){
			int x; cin >> x;
			events.pb(Event(0, i, i, x));
		}
		rep(orig_index, q){
			int l, r; cin >> l >> r;
			l--, r--;
			events.pb(Event(1, l, r, orig_index));
		}
		sort(all(events));
		SegTree ST = SegTree(n);
		umap<int, int> last = umap<int, int>();
		for(const Event& event : events){
			if (event.type == 0){
				if (last.find(event.val) != last.end()){
					ST.update(last[event.val], 0);
				}
				last[event.val] = event.start;
				ST.update(event.start, 1);
			}else{
				int cnt = ST.range_sum(event.start, event.end);
				ans[event.val] = cnt;
			}
		}
		rep(i, isize(ans)){
			cout << ans[i] << "\n";
		}
	}

Measured memory_bytes: 56772