#include<bits/stdc++.h>
#define rep(i,n) for (long long i = 0; i < (n); ++i)

using namespace std;

long long N, Q;
long long C[500005];

// (L, R), Query ID
vector<pair<pair<long long, long long>, long long> >LR;

vector<pair<long long, long long> >points;

/*
 *範囲の和を取得
 */
//区間[l, r)
struct segtree {
	vector<long long> data;
	long long n;
	segtree(long long nin){
		n = pow( 2, ceil( log(nin) / log(2) ) );
		long long size = 2 * n - 1;
		this->data.resize(size, 0);
	}

	//API for update val
	void update(long long idx, long long val){
		update(idx, val, 0, 0, n);
	}

	long long update(long long idx, long long val, long long node_id, long long left, long long right){
		//if query idx is within range return val
		if( !( left <= idx && idx < right ) ){
			return data[node_id];
		}
		if( left + 1 < right ) {
			//when node range is not 1, get update children val and update node data
			long long mid = (left + right) / 2 ;
			long long L = update(idx, val, 2 * node_id + 1, left, mid);
			long long R = update(idx, val, 2 * node_id + 2, mid, right);
			data[node_id] = L + R;
		} else {
			//when node range is 1, update node data
			data[node_id] = data[node_id] + val;
		}
		return data[node_id];
	}
	
	//API for get value of [l, r)
	long long get(long long l, long long r){
		return get(l, r, 0, 0, n);
	}

	/*
	 *internaly used function
	 *query_l: query left range
	 *query_r: query right range
	 *node_id: node id of 
	 *node_l:  node left range 
	 *node_r:  node right range
	 */
	long long get(long long query_l, long long query_r, long long node_id, long long node_l, long long node_r){
		//query range is outside of node range: return INF
		if( query_r <= node_l || node_r <= query_l ){
			return 0;
		}
		//query range is within node range: return node val
		if( query_l <= node_l && node_r <= query_r ){
			return data[node_id];
		}
		long long mid = (node_l + node_r) / 2;
		long long L = get(query_l, query_r, 2 * node_id + 1, node_l, mid);
		long long R = get(query_l, query_r, 2 * node_id + 2, mid, node_r);
		return L + R;
	}
};



long long ans[500005];

int main(){
	cin >> N >> Q;
	rep(i, N) cin >> C[i];
	rep(i, Q) {
		long long l, r;
		cin >> l >> r;l--;r--;
		LR.push_back(make_pair(make_pair(l, r), i));
	}

	map<long long, long long> memo;
	rep(i, N) {
		if(memo.count(C[i]) == 0) {
			memo[C[i]] = i;
			continue;
		}

		points.push_back(make_pair(memo[C[i]], i));
		memo[C[i]] = i;
	}

	sort(LR.begin(), LR.end(), greater<pair<pair<long long, long long>, long long> >());
	sort(points.begin(), points.end(), greater<pair<long long, long long> >());

	//cout << "LR" << endl;
	//rep(i, LR.size()) {
	//	cout << LR[i].first.first << "," << LR[i].first.second << " " << LR[i].second << endl;
	//}

	//cout << "points" << endl;
	//rep(i, points.size()) {
	//	cout << points[i].first << "," << points[i].second << endl;
	//}




	long long i = 0;
	long long j = 0;

	segtree sg(N + 3);

	while(1) {
		if(i >= LR.size()) {
			break;
		}

		if(j >= points.size()) {
			long long nextqueryL = LR[i].first.first;
			long long nextqueryR = LR[i].first.second;
			long long nextqueryID = LR[i].second;
			ans[nextqueryID] = nextqueryR - nextqueryL + 1 - sg.get(0, nextqueryR + 1);
			i++;
			continue;
		}

		long long nextqueryL = LR[i].first.first;
		long long nextqueryR = LR[i].first.second;
		long long nextqueryID = LR[i].second;

		long long nextDataL = points[j].first;
		long long nextDataR = points[j].second;

		if(nextqueryL > nextDataL) {
			ans[nextqueryID] = nextqueryR - nextqueryL + 1 - sg.get(0, nextqueryR + 1);
			i++;
		} else if(nextqueryL < nextDataL) {
			sg.update(nextDataR, 1);
			j++;
		} else if(nextqueryL == nextDataL) {
			sg.update(nextDataR, 1);
			//ans[nextqueryID] = nextqueryR - nextqueryL + 1 - sg.get(0, nextqueryR + 1);
			//i++;
			j++;
		}
	}

	rep(i, Q) {
		cout << ans[i] << endl;
	}

}

Measured memory_bytes: 62772