#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;
 
typedef long long ll;
typedef long double ld;
typedef double db; //
typedef string str; //
//
typedef pair<int,int> pi;
typedef pair<ll,ll> pl; //
typedef pair<db,db> pd; //
//
typedef vector<int> vi; 
typedef vector<ll> vl; //
typedef vector<db> vd; //
typedef vector<str> vs; //
typedef vector<pi> vpi;
typedef vector<pl> vpl; //
typedef vector<pd> vpd; //
 
typedef tree<pi, null_type, less<pi>, rb_tree_tag, tree_order_statistics_node_update> indexed_set;
 
#define mp make_pair
#define f first
#define s second
#define sz(x) (int)x.size()
#define all(x) begin(x), end(x)
#define rall(x) (x).rbegin(), (x).rend() //
#define rsz resize
#define ins insert //
#define ft front() //
#define bk back()
#define pf push_front //
#define pb push_back
#define eb emplace_back //
#define lb lower_bound //
#define ub upper_bound //
 
#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define F0R(i,a) FOR(i,0,a)
#define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i)
#define R0F(i,a) ROF(i,0,a)
#define trav(a,x) for (auto& a: x)
 
const int MOD = 1e9+7; // 998244353;
const int MX = 2e5+5; //
const ll INF = 1e18; //
const ld PI = acos((ld)-1);
const int xd[4] = {1,0,-1,0}, yd[4] = {0,1,0,-1}; //
mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count()); //
//
template<class T> bool ckmin(T& a, const T& b) { 
	return b < a ? a = b, 1 : 0; }
template<class T> bool ckmax(T& a, const T& b) { //
	return a < b ? a = b, 1 : 0; } //
constexpr int pct(int x) { return __builtin_popcount(x); } //
constexpr int bits(int x) { return 31-__builtin_clz(x); } // floor(log2(x)) //
constexpr int cdiv(int a, int b) { return a/b+!(a<0||a%b == 0); } // division of a by b rounded up, assumes b > 0 //
// IGNORE
int fstTrue(function<bool(int)> f, int lo, int hi) {
	hi ++; assert(lo <= hi); // assuming f is increasing
	while (lo < hi) { // find first index such that f is true 
		int mid = (lo+hi)/2; 
		f(mid) ? hi = mid : lo = mid+1; 
	} 
	return lo;
}
template<class T> void remDup(vector<T>& v) { 
	sort(all(v)); v.erase(unique(all(v)),end(v)); }
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);
    }
};
// IGNORE
//
int bit[500001];

int sum(int k){
	int s = 0;
	while(k >= 1){
		s += bit[k];
		k -= k & -k;
	}
	return s;
}

void upd(int k, int x){
	while(k <= 500000){
		bit[k] += x;
		k += k & -k;
	}
}

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int N, Q;
	cin >> N >> Q;
	int col[500001];
	queue<int> color[500001];
	int arr[500001];
	memset(arr, 0, sizeof arr);
	FOR(a, 1, N + 1){
		cin >> col[a];
		color[col[a]].push(a);
	}
	trav(a, color)
		if(sz(a)){
			upd(a.front(), 1);
			arr[a.front()]++;
			a.pop();
		}
	vector<pair<pi, int>> qu;
	F0R(a, Q){
		int l, r;
		cin >> l >> r;
		qu.pb({{l, r}, a});
	}
	sort(all(qu));
	int idx = 0;
	int ans[Q];
	trav(q, qu){
		while(idx < q.f.f - 1){
			idx++;
			if(arr[idx])
				upd(idx, -1);
			if(sz(color[col[idx]])){
				upd(color[col[idx]].front(), 1);
				arr[color[col[idx]].front()]++;
				color[col[idx]].pop();
			}
		}
		ans[q.s] = sum(q.f.s);
	}
	trav(a, ans)
		cout << a << endl;
}

Measured memory_bytes: 354992