#include <bits/stdc++.h>
using namespace std;
const int MX = 5e5 + 5;
const int sz = 705;
int ans = 0;
struct Node{
int l,r,idx;
};
int A[MX];
int cnt[MX];
void add(int idx){
cnt[A[idx]]++;
if(cnt[A[idx]] == 2)
ans++;
if(cnt[A[idx]] == 3)
ans--;
}
void remove(int idx){
cnt[A[idx]]--;
if(cnt[A[idx]] == 2)
ans++;
if(cnt[A[idx]] == 1)
ans--;
}
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
int N,M; cin >> N >> M;
vector<int> B(N);
for(int i = 0; i < N; i++){
cin >> A[i];
B[i] = A[i];
}
sort(B.begin(), B.end());
B.erase(unique(B.begin(), B.end()), B.end());
for(int i = 0; i < N; i++)
A[i] = lower_bound(B.begin(), B.end(), A[i]) - B.begin();
vector<Node> Q(M);
for(int i = 0; i < M; i++){
cin >> Q[i].l >> Q[i].r;
Q[i].l--; Q[i].r--;
Q[i].idx = i;
}
sort(Q.begin(), Q.end(), [&](const Node &a, const Node &b){
if((a.l / sz) != (b.l / sz)) return (a.l / sz) < (b.l / sz);
return ((a.l / sz) & 1 ? a.r < b.r : a.r > b.r);
});
int L = 0, R = -1;
vector<int> out(M);
for(int i = 0; i < M; i++){
while(R < Q[i].r) add(++R);
while(L > Q[i].l) add(--L);
while(R > Q[i].r) remove(R--);
while(L < Q[i].l) remove(L++);
out[Q[i].idx] = ans;
}
for(int i = 0; i < M; i++)
cout << out[i] << '\n';
return 0;
}
