#include "bits/stdc++.h"
using namespace std;
#define intt long long
#define fi first
#define se second
const intt mxN = 5e5+1;
const intt LG = 20;
const intt inf = 1e18;
intt n, q;
vector<intt> a(mxN), mp(mxN);
struct qry {
intt l, r, idx;
};
vector<qry>qs;
intt sz = 800;
bool cmp(qry &a, qry &b) {
if(a.l / sz == b.l / sz) {
return a.r < b.r;
}
return a.l / sz < b.l / sz;
}
intt ans;
void add(intt x) {
if(mp[x] == 2) ans--;
mp[x]++;
if(mp[x] == 2) ans++;
}
void remove(intt x) {
if(mp[x] == 2) ans--;
mp[x]--;
if(mp[x] == 2) ans++;
}
void _() {
cin >> n >> q;
sz = sqrt(n);
map<intt,intt> z,x;
for(intt i = 1; i <= n; i++) {
cin >> a[i];
z[a[i]]++;
}
intt avil=0;
for(auto u:z){
x[u.fi]=++avil;
}
for(intt i=0;i<n;i++) a[i]=x[a[i]];
for(intt i = 0; i < q; i++) {
intt a, b;
cin >> a >> b;
qs.push_back({a, b, i});
}
sort(qs.begin(), qs.end(), cmp);
vector<intt> c(q);
intt l = 1, r = 0;
for(intt i = 0; i < q; i++) {
intt curl = qs[i].l, curr = qs[i].r;
// cout << l << " " << r << " : " << curl << " " << curr << endl;
while(r < curr) {
r++;
add(a[r]);
}
while(l > curl) {
l--;
add(a[l]);
}
while(l < curl) {
remove(a[l]);
l++;
}
while(r > curr) {
remove(a[r]);
r--;
}
c[qs[i].idx] = ans;
}
for(intt i = 0; i < q; i++) {
cout << c[i] << endl;
}
cout << endl;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
// freopen("checklist.in", "r", stdin);
// freopen("checklist.out", "w", stdout);
intt t = 1, buu = 1;
// cin >> t;
while(t--){
// cout << "Case #" << buu++ << ": ";
_();
}
}
