#include<bits/stdc++.h>
using namespace std;
using ll = int;
const ll N = 5e5 + 2;
ll a[N], block, ans[N], cnt = 0;
ll A[N];
struct Mo {
ll lo, hi, ind;
};
bool cmp(Mo A, Mo B) {
if ((A.lo-1)/block != (B.lo-1)/block) return A.lo < B.lo;
return A.hi < B.hi;
}
void Add(ll x) {
if ( A[a[x]] == 2) cnt --;
A[a[x]] ++;
if ( A[a[x]] == 2) cnt ++;
return ;
}
void Remove(ll x) {
if ( A[a[x]] == 2) cnt --;
A[a[x]] --;
if ( A[a[x]] == 2) cnt ++;
return ;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
ll n, m, r,s, l,lo,hi, mx_x, y_val, i, j, t, q;
cin >> n >> q;
block = sqrtl(n);
map < ll, ll > mp_1, mp_2;
for (i = 1; i <= n; i ++){
cin >> a[i];
mp_1[a[i]] ++;
}
s = 0;
for ( auto R : mp_1) {
mp_2[R.first] = s;
s ++;
}
for (i = 1; i <= n; i ++) a[i] = mp_2[a[i]];
vector < Mo > v;
for (i = 1; i <= q; i ++) {
cin >> l >> r;
v.push_back({l, r, i});
}
sort(v.begin(), v.end(), cmp);
lo = 1;
hi = 0;
for (i = 0; i < v.size(); i ++) {
l = v[i].lo;
r = v[i].hi;
while (lo < l) {
Remove(lo);
lo ++;
}
while ( lo > l) {
lo --;
Add(lo);
}
while ( hi < r) {
hi ++;
Add(hi);
}
while ( hi > r) {
Remove(hi);
hi --;
}
ans[v[i].ind] = cnt;
}
for (i = 1; i <= q; i ++) {
cout << ans[i] << "\n";
}
}
