#include <bits/stdc++.h>
using namespace std;
#define int long long
const int MAX = 5e5 + 5;
struct wifi {
int n;
vector<int> BIT;
wifi(int n) : n(n) {
BIT.assign(n + 5, 0);
}
void update(int i, const int &val) {
for (; i <= n; i += -i & i) BIT[i] += val;
}
int get(int i) {
int res = 0;
for (; i > 0; i -= -i & i) res += BIT[i];
return res;
}
};
vector<int> nen;
int a[MAX], ans[MAX], pre[MAX], posi[MAX];
vector<pair<int, int>> query[MAX];
int32_t main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
// freopen("btd.inp", "r", stdin); freopen("btd.out", "w", stdout);
int n, q;
cin >> n >> q;
for (int i = 1; i <= n; i++) {
cin >> a[i];
nen.push_back(a[i]);
}
for (int i = 0; i < q; i++) {
int l, r;
cin >> l >> r;
query[r].emplace_back(l, i);
}
sort(nen.begin(), nen.end());
nen.erase(unique(nen.begin(), nen.end()), nen.end());
wifi waifu(n);
for (int r = 1; r <= n; r++) {
a[r] = lower_bound(nen.begin(), nen.end(), a[r]) - nen.begin() + 1;
if (posi[a[r]]) {
pre[r] = posi[a[r]];
waifu.update(pre[r], 1);
if (pre[pre[r]]) waifu.update(pre[pre[r]], -2);
if (pre[pre[pre[r]]]) waifu.update(pre[pre[pre[r]]], 1);
}
posi[a[r]] = r;
for (auto &cur : query[r]) {
int l, id;
tie(l, id) = cur;
ans[id] = waifu.get(r) - waifu.get(l - 1);
}
}
for (int i = 0; i < q; i++) {
cout << ans[i] << '\n';
}
return 0;
}
