/* 
	Author: ankrypt
*/

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;
template<class T> using oset=tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

#define MOD 1000000007
#define ll long long int
#define u64 unsigned long long int
#define ff first
#define ss second
#define all(x) x.begin(), x.end() 
#define ub upper_bound
#define lb lower_bound
#define MAX_INT 500005
#define PI 3.141592653589793
#define trace1(x)                cerr<<#x<<": "<<x<<endl
#define trace2(x, y)             cerr<<#x<<": "<<x<<" | "<<#y<<": "<<y<<endl
#define trace3(x, y, z)          cerr<<#x<<":" <<x<<" | "<<#y<<": "<<y<<" | "<<#z<<": "<<z<<endl
#define trace4(a, b, c, d)       cerr<<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<endl
#define trace5(a, b, c, d, e)    cerr<<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<" | "<<#e<< ": "<<e<<endl
#define trace6(a, b, c, d, e, f) cerr<<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<" | "<<#e<< ": "<<e<<" | "<<#f<<": "<<f<<endl
#define go ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define fi(a, b, c, d) for(ll a = b; a < c; a += d)
#define fl(a, b, c, d) for(ll a = b; a < c; a += d)
#define fei(a, b, c, d) for(ll a = b; a <= c; a += d)
#define fel(a, b, c, d) for(ll a = b; a <= c; a += d)
#define quit exit(0)
#define mem(x, a) memset(x, a, sizeof x)
#define pii pair<ll, ll>
#define pll pair<ll, ll>
#define pcl pair<char, ll>
#define psl pair<string, ll>


ll N, M, A, B, C;
ll arr[MAX_INT], arr1[MAX_INT], data[MAX_INT];
vector<pair<ll, pair<ll, ll>>> V;
unordered_map<ll, ll> mp;
set<ll> s;
string S = "";
ll cases;

  
bool comp(pair<ll, pair<ll, ll>> &X, pair<ll, pair<ll, ll>> &Y) { 
	if(X.ss.ff == Y.ss.ff) {
		return X.ff > Y.ff;
	}
    return X.ss.ff < Y.ss.ff; 
} 
  
void _update(ll ind, ll val, ll BIT[], ll n) { 
    for (; ind <= n; ind += ind&-ind) 
        BIT[ind] += val; 
} 
  
ll _query(ll ind, ll BIT[], ll n) { 
    ll sum = 0; 
    for (; ind>0; ind-=ind&-ind) 
        sum += BIT[ind]; 
    return sum; 
} 
  
void solve(ll arr[], ll n, vector<pair<ll, pair<ll, ll>>> queries, ll sz) 
{ 
    ll BIT[n+1]; 
    memset(BIT, 0, sizeof(BIT)); 
  
    ll vis[MAX_INT]; 
    memset(vis, -1, sizeof(vis)); 
  
    ll answer[sz]; 
    ll ctr = 0; 
    for (ll i = 0; i < n; i++) { 
        if (vis[arr[i]] !=-1) 
            _update (vis[arr[i]] + 1, -1, BIT, n); 
  
        vis[arr[i]] = i; 
        _update(i + 1, 1, BIT, n); 
  
        while (ctr < sz && queries[ctr].ss.ff == i) { 
            answer[queries[ctr].ss.ss] = _query(queries[ctr].ss.ff + 1, BIT, n) - _query(queries[ctr].ff, BIT, n); 
            ctr++; 
        } 
    } 
    for (ll i = 0; i < sz; i++) 
        cout << answer[i] << endl; 
} 
  


int main() {
	go;
    cin >> N >> M;
    fi(i, 0, N, 1) {
    	cin >> arr[i];
    }
    fi(i, 0, M, 1) {
    	cin >> A >> B;
    	A--;
    	B--;
    	V.push_back({A, {B, i}});
    }
    sort(V.begin(), V.end(), comp);
    ll sz = V.size();
    solve(arr, N, V, sz);
    
	return 0;
}
/*
	Powered by Buggy Plugin
*/




Measured memory_bytes: 42964