#include <bits/stdc++.h>
using namespace std;
const int N = 5e5 + 10;
const int block = 400;
int a[N];
int freq[N];
int ans[N];
struct queries{
int i,l,r;
} qq[N];
int n,q;
int temp = 0;
inline void add(int i){
if(freq[a[i]] == 2)
temp--;
freq[a[i]]++;
if(freq[a[i]] == 2)
temp++;
}
inline void remove(int i){
if(freq[a[i]] == 2)
temp--;
freq[a[i]]--;
if(freq[a[i]] == 2)
temp++;
}
signed main(){
iostream::sync_with_stdio(false);
cin.tie(nullptr);cout.tie(nullptr);
cin >> n >> q;
for(int i = 0;i<n;i++)cin >> a[i];
for(int i = 0;i<q;i++){
cin >> qq[i].l >> qq[i].r;
qq[i].l--;
qq[i].r--;
qq[i].i = i;
}
sort(qq,qq + q,[&](queries a,queries b){
int ab = a.l/block;
int bb = b.l/block;
if(ab == bb){
if(ab%2 == 0)
return a.r < b.r;
else
return a.r > b.r;
}
else
return ab < bb;
});
int l = 0,r = -1;
for(int i = 0;i<q;i++){
while(r < qq[i].r){
r++;
add(r);
}
while(l > qq[i].l){
l--;
add(l);
}
while(r > qq[i].r){
remove(r);
r--;
}
while(l < qq[i].l){
remove(l);
l++;
}
ans[qq[i].i] = temp;
}
for(int i = 0;i<q;i++)
cout << ans[i] << "\n";
}
