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

#define fastio 			ios::sync_with_stdio(0);	cin.tie(0); cout.tie(0);  cout<<fixed;  cout<<setprecision(12);
#define randomINT 		mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
#define	newl 			cout<<"\n"
#define DISP(as)		for(auto it : as) cout<<it<<" ";newl;
#define all(x)         	(x).begin(),(x).end()
#define mset(x,val)    	memset(x,val,sizeof(x))
#define newl           	cout<<"\n"
#define pb             	push_back
#define mp             	make_pair
#define f 				first
#define s 				second
#define dline          cerr<<"///REACHED///\n";
#define deb1(x)        cerr<<#x<<" = "<<x<<'\n';
#define deb2(x,y)      cerr<<'['<<#x<<','<<#y<<"] = "<<'['<<x<<','<<y<<']'<<'\n';
#define deb3(x,y,z)    cerr<<'['<<#x<<','<<#y<<','<<#z<<"] = "<<'['<<x<<','<<y<<','<<z<<']'<<'\n';
#define N 1000000007 // prime modulo value 

typedef long long 				ll;
typedef long double 			ld;
typedef vector<ll> 				vll;
typedef pair<ll , ll> 			pll;
typedef pair<ld, ld> 			pld;
typedef unordered_map<ll, ll> 	um;
typedef vector<pll> 			vpll;

const ll 	MAX5 	= 	1e+5 + 7;
const ll 	MAX7 	= 	1e+7 + 7;
const ll 	MAXN 	= 	MAX7;
const ll   	INF   	=  	0x7f7f7f7f7f7f7f7f;
const int  	INFi 	=  	0x7f7f7f7f;
const ll 	MOD		=  	1e9 + 7;


// <------------- Declare Variables Here ------------> //

ll T = 1;
ll n, x, k,  m, y, q ;
string s, t;
ld w;

// <------------- Implement Functions Here ----------> //

ll tree[4000000];
ll a[600000];
ll arr[600000];
ll pos[600000];
ll quer[600000];
vector<pair<pll,ll>> ans;

bool comp(pair<pll,ll> &a,pair<pll,ll> &b) {
	if(a.f.s == b.f.s && a.f.f == b.f.f) return a.s < b.s;
	if(a.f.s == b.f.s) return a.f.f < b.f.f;
	return a.f.s < b.f.s;
}

void build(ll start=1 , ll end=n , ll node=1) {
	if (start == end) {

		tree[node] = a[start];
	}
	else {
		ll mid = (start + end) / 2;
		build(start, mid, 2 * node);
		build(mid + 1, end, 2 * node + 1);
		tree[node] = tree[2 * node] + tree[2 * node + 1];
	}
}

void update(ll indx, ll val, ll start = 1 , ll end = n , ll node = 1) {
	if (start == end) {
		a[indx] = val;
		tree[node] = val;
	}
	else {
		ll mid = (start + end) / 2;
		if (start <= indx && indx <= mid) update( indx, val, start, mid, 2 * node);
		else 							update(indx, val, mid + 1, end, 2 * node + 1);
		tree[node] = tree[2 * node] + tree[2 * node + 1];
	}
}

ll query(ll l, ll r, ll start = 1, ll end = n , ll node = 1) {
	if (r < start || end < l) return 0;
	else if (l <= start && end <= r) {
		return tree[node];
	}
	else {
		ll mid = (start + end) / 2;
		ll p1 = query(l, r, start, mid, 2 * node);
		ll p2 = query(l, r, mid + 1, end, 2 * node + 1);
		return p1 + p2;
	}
}

// <------------- Start of main() -------------------> //

void MAIN() {
	cin >> n >> q;
	for(ll i=1;i<=n;i++) cin>>arr[i];

	for(ll i=0;i<q;i++) {
		cin>>x>>y;
		ans.pb({{x,y},i});
	}

	sort(all(ans),comp);
	build();
	ll cur = 1;

	/*for(auto it : ans) {
		cout<<it.f.f<<" "<<it.f.s<<"\n";
	}*/

	for(ll i=0;i<q;i++) {
		for(ll j = cur;j <= ans[i].f.s; j++) {
			update(pos[arr[j]],0);
			pos[arr[j]] = j;
			update(j,1);
		}
		cur = ans[i].f.s;
		//for(ll i=1;i<=n;i++) cout<<a[i]<<" ";newl;
		quer[ans[i].s] = query(ans[i].f.f,ans[i].f.s);
	}

	for(ll i=0;i<q;i++) {
		cout<<quer[i]<<"\n";
	}
}

int main() {
	fastio; randomINT;
	//cin >> T;
	while (T--) {
		MAIN();
	}
	return 0;
}

Measured memory_bytes: 39484