// #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;
 
struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        // http://xorshift.di.unimi.it/splitmix64.c
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};

// 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, custom_hash> last = umap<int, int, custom_hash>();
	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: 56724