#include <bits/stdc++.h>
using namespace std;
constexpr int BLOCK = 700;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, q;
cin >> n >> q;
vector<int> a(n);
for (int i = 0; i < n; i++) {
cin >> a[i];
}
auto b = a;
ranges::sort(b);
b.erase(unique(b.begin(), b.end()), b.end());
for (auto &x : a) {
x = ranges::lower_bound(b, x) - b.begin();
}
vector<array<int, 3>> qs(q);
for (int i = 0; i < q; i++) {
cin >> qs[i][0] >> qs[i][1];
qs[i][0]--; qs[i][1]--;
qs[i][2] = i;
}
sort(qs.begin(), qs.end(), [&](auto x, auto y) {
if (x[0] / BLOCK != y[0] / BLOCK) {
return x[0] / BLOCK < y[0] / BLOCK;
}
if ((x[0] / BLOCK) & 1) {
return x[1] < y[1];
} else {
return x[1] > y[1];
}
});
int res = 0;
vector<int> cnt(n);
auto add = [&](int x) {
if (cnt[x] == 1) res++;
if (cnt[x] == 2) res--;
cnt[x]++;
};
auto rem = [&](int x) {
if (cnt[x] == 3) res++;
if (cnt[x] == 2) res--;
cnt[x]--;
};
vector<int> ans(q);
int l = 0, r = -1;
for (auto [tl, tr, i] : qs) {
while (r < tr) add(a[++r]);
while (r > tr) rem(a[r--]);
while (l > tl) add(a[--l]);
while (l < tl) rem(a[l++]);
ans[i] = res;
}
for (int i = 0; i < q; i++) {
cout << ans[i] << '\n';
}
return 0;
}
