#include <bits/stdc++.h>
	#include <cstdio>
	#include <cstring>
	#include <cmath>
	#include <cstring>
	#include <chrono>
	#include <complex>
	#define endl "\n"	
	typedef long long LL;
	#define ll long long int
	#define vi vector<int>
	#define vll vector<ll>
	#define vvi vector < vi >
	#define pii pair<int,int>
	#define pll pair<long long, long long>
	#define mod 1000000007
	#define mod2 998244353
	#define inf 1000000000000000001;
	#define all(c) c.begin(),c.end()
	#define sz(v) ((ll)(v).size())
	#define mp(x,y) make_pair(x,y)
	#define mem(a,val) memset(a,val,sizeof(a))
	#define eb emplace_back
	#define pb push_back
	#define f first
	#define s second
	#define dbg(a) cout<<#a<<" --> "<<(a)<<"\n";
	#define forn(i,n) for (ll i=0; i<(n); ++i)
	#define fornd(i,n) for (ll i=(n)-1; i>=0; --i)	
	#define forab(i,a,b) for (ll i=(a); i<=(b); ++i)
	#define read(a) ll a; cin >> a;
	#define reads(s) string s; cin >> s;
	#define readb(a, b) ll a, b; cin >> a >> b;
	#define readc(a, b, c) ll a, b, c; cin >> a >> b >> c;
	#define readarr(a, n) int a[(n) + 1] = {}; forab(i, 0, (n-1)) {cin >> a[i];}
	#define readmat(a, n, m) int a[n + 1][m + 1] = {}; forab(i, 1, n) {forab(j, 1, m) cin >> a[i][j];}
	#define readv(A,n) vll A(n,0); forn(i,n) cin>>A[i]; 
	#define print(a) cout << a << endl;
	#define printarr(a, n) forab (i, 1, n) cout << a[i] << " "; cout << endl;
	#define printv(v) for (int i: v) cout << i << " "; cout << endl;
	#define printmat(a, n, m) forab(i, 1, n) {forab (j, 1, m) cout << a[i][j] << " "; cout << endl;}
	 
	#define fast_io ios_base::sync_with_stdio(false),cin.tie(NULL),cout.tie(NULL)
	using namespace std;
	bool isPowerOfTwo(int x) {
    return x && (!(x & (x - 1)));
	}
	int takemod(int x) {
    return (x % mod + mod) % mod;
	}
 
	int fpow(int base, int power, int MOD) {
    int result = 1;
    base = base % MOD;
    while (power) {
        if (power & 1)
            result = (result * base) % MOD;
        base = (base * base) % MOD;
        power = power >> 1;
    }
    return result;
	}
 	struct Query
 	{
 		ll l,r,idx;
 	};
 		bool sortbysec(const Query &a, const Query &b) 
 	 	{ 
 	 	    return (a.r < b.r); 
 	 	} 	
	int modinv(int x) {return fpow(x, mod - 2, mod);}
	const int N=1000010;
	ll fen[N];
	void update(ll i,ll a)
	{
		while(i<N)
		{
			fen[i]+=a;
			i+=(i)&(-i);
		}
	}
	ll sum(ll i)
	{
		ll sum=0;
		while(i>0)
		{
			sum+=fen[i];
			i-=(i)&(-i);
		}
		return sum;
	}
	ll vis[N];

	void solve()
	{
		mem(fen,0);
		mem(vis,-1);
		ll n,q;
		cin>>n>>q;
		vll A(n);
		forn(i,n)cin>>A[i];
		Query quries[q];
		forn(i,q)
		{
			cin>>quries[i].l>>quries[i].r;
			quries[i].idx=i;
			quries[i].l--;
			quries[i].r--;
		}	
		sort(quries,quries+q,sortbysec);
		ll ans[q];
		ll query_counter=0;
		for (int i=0; i<n; i++) 
  		  { 
        // If last visit is not -1 update -1 at the 
        // idx equal to last_visit[arr[i]] 
        if (vis[A[i]] !=-1) 
            update (vis[A[i]] + 1, -1); 
  
        // Setting last_visit[arr[i]] as i and updating 
        // the bit array accordingly 
        vis[A[i]] = i; 
        update(i + 1LL, 1LL); 
  
        // If i is equal to r of any query  store answer 
        // for that query in ans[] 
        while (query_counter < q && quries[query_counter].r == i) 
        { 
            ans[quries[query_counter].idx] = 
                     sum(quries[query_counter].r +1LL)- 
                     sum(quries[query_counter].l); 
            query_counter++; 
        } 
    } 
  
    // print answer for each query 
    for (int i=0; i<q; i++) 
        cout << ans[i] << endl; 
	}
	int main()
	{	
		#ifndef ONLINE_JUDGE
		freopen("input.txt","r",stdin);
		freopen("output.txt","w",stdout);
		#endif
		fast_io;
		int T=1;
		//cin>>T;
		// cin.ignore(); must be there when using getline(cin, s)
		while(T--)
		{
			solve();
		}
		return 0;
	}

	
	

Measured memory_bytes: 38944