#include <bits/stdc++.h>
using namespace std;
#define all(x) x.begin(), x.end()
#define ll long long
#define V vector
#define FASTIO ios_base::sync_with_stdio(false); cin.tie(nullptr);
struct Query {
int l, r, id;
};
int main() {
FASTIO
int n, q;
cin >> n >> q;
int sq = max(1, (int)sqrt(n));
V<int> a(n + 1);
for (int i = 1; i <= n; i++)
cin >> a[i];
V<int> comp(a.begin() + 1, a.end());
sort(all(comp));
comp.erase(unique(all(comp)), comp.end());
for (int i = 1; i <= n; i++)
a[i] = lower_bound(all(comp), a[i]) - comp.begin() + 1;
V<Query> queries(q);
for (int i = 0; i < q; i++) {
cin >> queries[i].l >> queries[i].r;
queries[i].id = i;
}
sort(all(queries), [&](const Query &A, const Query &B) {
int blockA = (A.l - 1) / sq;
int blockB = (B.l - 1) / sq;
if (blockA != blockB)
return blockA < blockB;
if (blockA & 1)
return A.r > B.r;
return A.r < B.r;
});
V<int> cnt(n + 1, 0);
V<int> ans(q);
int cur = 0;
int L = 1, R = 0;
auto add = [&](int pos) {
if (cnt[a[pos]] == 2)
--cur;
cnt[a[pos]]++;
if (cnt[a[pos]] == 2)
++cur;
};
auto remove = [&](int pos) {
if (cnt[a[pos]] == 2)
--cur;
cnt[a[pos]]--;
if (cnt[a[pos]] == 2)
++cur;
};
for (auto &qr : queries) {
while (R < qr.r) add(++R);
while (R > qr.r) remove(R--);
while (L < qr.l) remove(L++);
while (L > qr.l) add(--L);
ans[qr.id] = cur;
}
for (int i = 0; i < q; i++)
cout << ans[i] << "\n";
return 0;
}
