#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const ll N = 5e5 + 2;
ll a[N], block, ans[N], cnt = 0;
unordered_map < ll, ll > A;
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() {
ll n, m, r, l,lo,hi, mx_x, y_val, i, j, t, q;
cin >> n >> q;
block = sqrtl(n);
for (i = 1; i <= n; i ++){
cin >> 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";
}
}
