#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ll long long
#define ar array
#define ld long double
const int N = 5e5 + 20;
const int MOD = 1e9 + 7;
const int K = 700;
const int INF = 1e17;
const int LOG = 34;
int ans = 0;
int cnt[N];
int A[N];
void add(int x){
x = A[x];
ans -= cnt[x] == 2;
cnt[x]++;
ans += cnt[x] == 2;
}
void rem(int x){
x = A[x];
ans -= cnt[x] == 2;
cnt[x]--;
ans += cnt[x] == 2;
}
bool cmp(ar<int, 3> a, ar<int,3 > b){
return ar<int,2>{a[0] / K, a[1]} < ar<int, 2>{b[0] / K, b[1]};
}
signed main(){ios::sync_with_stdio(false);cin.tie(0);
int n, q;
cin>>n>>q;
map<int,int> mp;
int id = 0;
for(int i = 0;i < n;i++){
cin>>A[i];
if(!mp.count(A[i]))mp[A[i]] = id++;
A[i] = mp[A[i]];
//cout<<A[i]<<" ";
}
//cout<<endl;
ar<int, 3> que[q];
for(int i = 0;i < q;i++){
cin>>que[i][0]>>que[i][1];
--que[i][0], --que[i][1];
que[i][2] = i;
}
int ml = 0;
int mr = -1;
sort(que, que + q, cmp);
int res[q];
for(int i = 0;i < q;i++){
int l = que[i][0];
int r = que[i][1];
int ind = que[i][2];
//cout<<i<<endl;
while(ml > l)add(--ml);
while(mr < r)add(++mr);
while(ml < l)rem(ml++);
while(mr > r)rem(mr--);
res[ind] = ans;
}
for(int i = 0;i < q;i++)cout<<res[i]<<" ";
}
// Te molam da raboti!
