#include<bits/stdc++.h>
#define ll long long
#define all(v) v.begin(),v.end()
#define PB push_back
#define PI 3.1415926535897932384626433832795
#define what(x) cout<<#x<<" is "<<x<<endl;
using namespace std;


template <typename A, typename B>
string to_string(pair<A, B> p);

template <typename A, typename B, typename C>
string to_string(tuple<A, B, C> p);

template <typename A, typename B, typename C, typename D>
string to_string(tuple<A, B, C, D> p);

string to_string(const string& s) {
  return '"' + s + '"';
}

string to_string(const char* s) {
  return to_string((string) s);
}

string to_string(bool b) {
  return (b ? "true" : "false");
}

string to_string(vector<bool> v) {
  bool first = true;
  string res = "{";
  for (int i = 0; i < static_cast<int>(v.size()); i++) {
    if (!first) {
      res += ", ";
    }
    first = false;
    res += to_string(v[i]);
  }
  res += "}";
  return res;
}

template <size_t N>
string to_string(bitset<N> v) {
  string res = "";
  for (size_t i = 0; i < N; i++) {
    res += static_cast<char>('0' + v[i]);
  }
  return res;
}

template <typename A>
string to_string(A v) {
  bool first = true;
  string res = "{";
  for (const auto &x : v) {
    if (!first) {
      res += ", ";
    }
    first = false;
    res += to_string(x);
  }
  res += "}";
  return res;
}

template <typename A, typename B>
string to_string(pair<A, B> p) {
  return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}

template <typename A, typename B, typename C>
string to_string(tuple<A, B, C> p) {
  return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " + to_string(get<2>(p)) + ")";
}

template <typename A, typename B, typename C, typename D>
string to_string(tuple<A, B, C, D> p) {
  return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " + to_string(get<2>(p)) + ", " + to_string(get<3>(p)) + ")";
}

void debug_out() { cerr << endl; }

template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
  cerr << " " << to_string(H);
  debug_out(T...);
}
#ifndef ONLINE_JUDGE
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 42
#endif

ll powmod(ll a,ll b,ll mod) {
    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;
}
const int mxn=5e5+1;
int fin[mxn];
int lst[mxn];
int n,q;
vector<int> c;
void update(int ind,int val){
		while(ind<=n){
			fin[ind]+=val;
			ind+=ind&-ind;
		}
}
int query(int ind){
	int ret=0;
	while(ind>0){
		ret+=fin[ind];
		ind-=ind&-ind;
	}
	return ret;
}

struct Query{
	int l,r,ind;
	bool operator()(Query a, Query b){
		return a.r<b.r;
	}
};

void solve(){
	memset(lst,-1,sizeof(lst));
	cin>>n>>q;
	int ans[q];
	c.resize(n);
	for(int i=0;i<n;i++){
		cin>>c[i];
	}
	Query qry[q];
	for(int i=0;i<q;i++){
		qry[i].ind=i;
		cin>>qry[i].l>>qry[i].r;
		qry[i].l--,qry[i].r--;
	}
	sort(qry,qry+q,Query());
	for(int j=0,i=0;i<n;i++){
		if(lst[c[i]]!=-1){
			update(lst[c[i]]+1,-1);
		}
		lst[c[i]]=i;
		update(i+1,1);
		while(j<q&&qry[j].r==i){
			ans[qry[j].ind]=query(qry[j].r+1)-query(qry[j].l);
			j++;
		}
	}
	for(int i=0;i<q;i++){
		cout<<ans[i]<<endl;
	}

}


int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int tc=1;
	#ifndef ONLINE_JUDGE
	freopen("input.txt","r",stdin);
	#endif
	// cin>>tc;
    while(tc--)solve();
}


Measured memory_bytes: 17436