#include <iostream>
#include <queue>
#include <assert.h>   
#include <vector>
#include <algorithm>
#include <time.h>
#include <numeric>
#include <string>
#include <cstring>
#include <stack>
#include <unordered_set>
#include <unordered_map>
#include <set>
#include <map>
#include <numeric>
#include <deque>
#include <iomanip>
#include <cstdlib>
#include <climits>
#include <cmath>
#include <cstdio>
using namespace std;


//#define double long double
//#define int long long
//#define int unsigned long long

#define ll long long
#define ld long double 
#define pi pair<int, int> 
#define pl pair<ll,ll>  
#define pd pair<ld,ld> 
#define str string  
#define mp make_pair
#define vi vector<int> 
#define vl vector<ll> 
#define vd vector<ld> 
#define vs vector<str> 
#define vpi vector<pi> 
#define vpl vector<pl> 
#define vpd vector<pd> 
#define si set<int> 
#define FF(i,j,n) for(signed i=j;i<=n;i++)  
#define DD(i,j,n) for(signed i=j;i>=n;i--) 
#define F(i,j,n) for(signed i=j;i<n;i++)   
#define D(i,j,n) for(signed i=j;i>n;i--) 
#define mem(a,b) memset(a,b,sizeof(a))
#define ndl cout << endl
#define ull unsigned long long 

const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3fLL;


#define sz(x) (signed)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 X first
#define Y second
#define pf push_front 
#define pb push_back
#define eb emplace_back 
#define lb lower_bound 
#define ub upper_bound 
#define IOS ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define SHOWVECTOR(v) {std::cerr << #v << "\t: ";for(const auto& xxx : v){std::cerr << xxx << " ";}std::cerr << "\n";}
#define SHOWVECTOR2(v) {std::cerr << #v << "\t:\n";for(const auto& xxx : v){for(const auto& yyy : xxx){std::cerr << yyy << " ";}std::cerr << "\n";}}
#define SHOWQUEUE(a) {auto tmp(a);std::cerr << #a << "\t: ";while(!tmp.empty()){std::cerr << tmp.front() << " ";tmp.pop();}std::cerr << "\n";}
#define SHOWSTACK(a) {auto tmp(a);std::cerr << #a << "\t: ";while(!tmp.empty()){std::cerr << tmp.top() << " ";tmp.pop();}std::cerr << "\n";}
//math

const int mod = 1e9 + 7;

ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
int pct(int x) { return __builtin_popcount(x); } 
int bit(int x) { return 31-__builtin_clz(x); } // floor(log2(x)) 
int cdiv(int a, int b) { return a/b+!(a<0||a%b == 0); } // division of a by b rounded up, assumes b > 0 



void DBG() { cerr << "]" << endl; }
template<class H, class... T> void DBG(H h, T... t) {
  cerr << to_string(h); if (sizeof...(t)) cerr << ", ";
  DBG(t...); }
#ifdef LOCAL 
#define dbg(...) cerr << "[" << #__VA_ARGS__ << "]: [", DBG(__VA_ARGS__)
#define HERE cout << "=====GOTHERE=====" << endl
#else
#define dbg(...) 42
#define HERE 42
#endif


 /* ============== END OF HEADER ============== */

const int N = 500005;
int n,_,q,k;
int m;
int c[N];
int maxn;
int sum = 0;
int ans[N];

int cnt[N];

struct query {
  int l, r, id;
  bool operator<(const query &x) const {
    if (l / maxn != x.l / maxn) return l < x.l;
    //奇偶排序，为了pointer防止过度震荡
    //奇数index r从小到大，偶数从大到小
    return (l / maxn) & 1 ? r < x.r : r > x.r;
  }
} a[N];

inline void add(int i){
	if(cnt[i]==0){
		sum +=1;
	}
	cnt[i]++;
}
inline void del(int i){
	if(cnt[i]==1){
		sum -= 1;
	}
	cnt[i]--;
}


void solve(){
	cin >> n >> m;
	FF(i,1,n){
		cin >> c[i];
	}
	maxn = sqrt(n);
	F(i,0,m){
		cin >> a[i].l >> a[i].r;
		a[i].id = i;
	}
	sort(a,a+m);
	for(int i = 0,l=1,r=0; i<m; i++){
		//这四个while顺序不能乱

		while (l > a[i].l) add(c[--l]);
	    while (r < a[i].r) add(c[++r]);
	    while (l < a[i].l) del(c[l++]);
	    while (r > a[i].r) del(c[r--]);

		// while(r > a[i].r) del(c[r--]);
		// while(r < a[i].r) add(c[++r]);
		// while (l > a[i].l) add(c[--l]);
		// while (l < a[i].l) del(c[l++]);

	    ans[a[i].id] = sum;
	}
	for(int i = 0; i < m; i++){
		cout << ans[i] << endl;
	}
}

signed main(){
  //clock_t t1 = clock();  
	IOS
	solve();
  
  //cout << "THE ALGORITHM TOOK: " << (clock() - t1) * 1.0 / CLOCKS_PER_SEC * 1000 << "ms"<< endl;
	return 0;
}

Measured memory_bytes: 15476