#include <iostream>
#include <cstdio>
#include <string.h>
#include <vector>
#include <limits>
#include <algorithm>
#include <stdlib.h>
#include <math.h>
#include <deque>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <assert.h>
#include <sstream>
#include <type_traits>
#define SET(x,y) x |= (1 << y)
#define CLEAR(x,y) x &= ~(1<< y)
#define READ(x,y) ((0u == (x & (1<<y)))?0u:1u)
#define TOGGLE(x,y) (x ^= (1<<y))
#define watch(x) cout << (#x) << " is " << (x) << endl
#define pb push_back
#define mp make_pair
#define si(n) scanf("%d",&n)
#define sf(n) scanf("%f",&n)
#define sl(n) scanf("%lld",&n)
#define slu(n) scanf("%llu",&n)
#define sd(n) scanf("%lf",&n)
#define ss(n) scanf("%s",n)
#define pnl printf("\n")
#define ll long long
#define pii pair<int, int>
#define pll pair<long long, long long>
#define pF first
#define pS second
#define CL(a,b) memset(a,b,sizeof(a))
#define sqr(x) ((x)*(x))
#define intLIMIT numeric_limits<int>
#define longLIMIT numeric_limits<long long>
#define GCD(a,b) __gcd((a),(b))
#define dbl(x) (double)(x)
#define vi vector <int>
#define vii vector < pair <int, int> >
#define vll vector <long long>
#define allof(x) (x).begin(), (x).end()
#define fastCin cin.sync_with_stdio(0);cin.tie(0)
#define scanUnsigned(x) do{while((x=getchar())<'0'); for(x-='0'; '0'<=(_=getchar()); x=(x<<3)+(x<<1)+_-'0');}while(0)
#define printArr(a,l) cout<<#a<<": ";for(int i=0;i<(l);i++){cout<<a[i]<<" ";}cout<<endl
#define print2dArr(a,r,c) cout<<#a<<":\n";for(int i=0;i<(r);i++){for(int j=0;j<(c);j++){cout<<a[i][j]<<" ";}cout<<endl;}
char _;
using namespace std;
void PRINT (int x, int y) { for (int i = y-1; i >= 0; i--) { cout << READ(x,i); } cout << endl; }

vector<string>vec_splitter(string s){s+=',';vector<string>res;while(!s.empty()){res.push_back(s.substr(0,s.find(',')));s=s.substr(s.find(',')+1);}
return res;}
void debug_out(vector<string>__attribute__((unused))args,__attribute__((unused))int idx,__attribute__((unused))int LINE_NUM){cerr<<endl;}
template<typename Head,typename...Tail>void debug_out(vector<string>args,int idx,int LINE_NUM,Head H,Tail...T){if(idx>0)cerr<<", ";else cerr<<"Line("<<LINE_NUM<<") ";stringstream ss;ss<<H;cerr<<args[idx]<<" = "<<ss.str();debug_out(args,idx+1,LINE_NUM,T...);}
#ifdef LOCAL_DBG
#define dbg(...) debug_out(vec_splitter(#__VA_ARGS__), 0, __LINE__, __VA_ARGS__)
#else
#define dbg(...) 42
#endif

int sz;

inline bool mo_cmp(const pair< pair<int, int>, int> &x,
        const pair< pair<int, int>, int> &y)
{
    int block_x = x.first.first / sz;
    int block_y = y.first.first / sz;
    if(block_x != block_y)
        return block_x < block_y;
    return x.first.second < y.first.second;
}

int ans[500005];

int main () {
	fastCin;
	int n, q;
	cin >> n >> q;
	sz = sqrt(n);
	vector < pair < pii, int> > m;
	int a[500005] = {0};
	for (int x = 0; x < n; x++) {
		cin >> a[x];
	}
	for (int x = 0; x < q; x++) {
		int l, r;
		cin >> l >> r;
		m.pb({{l-1,r-1}, x});
	}
	sort(allof(m), mo_cmp);
	int cL = 0, cR = -1;
	int cnt[500005] = {0}, tot = 0;
	for (int x = 0; x < q; x++) {
		int nxtL = m[x].pF.pF, nxtR = m[x].pF.pS;
		// dbg(nxtL,nxtR);
		while (cR < nxtR) {
			cR++;
			cnt[a[cR]]++;
			if (cnt[a[cR]]==1) {
				tot++;
			}
		}
		while (cR > nxtR) {
			cnt[a[cR]]--;
			if (cnt[a[cR]]==0) {
				tot--;
			}
			cR--;
		}
		while (cL < nxtL) {
			cnt[a[cL]]--;
			if (cnt[a[cL]]==0) {
				tot--;
			}
			cL++;
		}
		while (cL > nxtL) {
			cL--;
			cnt[a[cL]]++;
			if (cnt[a[cL]]==1) {
				tot++;
			}
		}
		ans[m[x].pS]=tot;
	}
	for (int x = 0; x < q; x++) {
		cout << ans[x] << "\n";
	}
	return 0;
}

Measured memory_bytes: 15600