#include<iostream>
#include<math.h>
#include<utility>
#include<map>
#include<string>
#include<algorithm>
#include<math.h>
#include<vector>
using namespace std;
#define int long long
#define ff first
#define ss second
#define pb push_back
const int S = 500;
const int N = 5e5+5;
int arr[N];
map<int,int>cmp;
int cnt=0;
int ans[N];
int val[N];
bool cmp2(pair<pair<int, int>, int> a, pair<pair<int, int>, int> b)
{
if (a.ff.ff / S != b.ff.ff / S) return a.ff.ff< b.ff.ff;
return (a.ff.ss < b.ff.ss)^(a.ff.ff/S%2);
}
void add(int a){
val[a]++;
if(val[a]==2){
cnt++;
}
}
void rem(int a){
val[a]--;
if(val[a]==1){
cnt--;
}
}
signed main(){
int n,q;
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>n>>q;
for(int i=1;i<=n;i++){
cin>>arr[i];
cmp[arr[i]];
}
int k=1;
for(auto it=cmp.begin() ; it!=cmp.end(); ++it){
it->ss = k++;
}
for(int i=1;i<=n;i++){
arr[i] = cmp[arr[i]];
}
vector<pair<pair<int, int>, int>> qq(q);
for (int i = 0; i < q; i++) {
int l, r;
cin >> l >> r;
qq[i] = {{l, r}, i};
}
sort(qq.begin(), qq.end(), cmp2);
int L = 0, R = -1;
for (int i = 0; i < q; i++) {
int j = qq[i].ss;
int l = qq[i].ff.ff;
int r = qq[i].ff.ss;
while (R < r) add(arr[++R]);
while (L > l) add(arr[--L]);
while (R > r) rem(arr[R--]);
while (L < l) rem(arr[L++]);
ans[j]=cnt;
}
for(int i=0;i<q;i++){
cout<<ans[i]<<'\n';
}
}
