#include <bits/stdc++.h>
#define int int64_t
const int N = 5e5 + 5;
struct fenwick {
int t[2 * N];
int query(int i) {
int ans = 0;
for(; i > 0; i -= i & - i) {
ans += t[i];
}
return ans;
}
void update(int i, int v) {
for(; i < N; i += i & - i) {
t[i] += v;
}
}
int query(int l, int r) {
return query(r) - query(l - 1);
}
}fenw;
void solve() {
int n, q;
std::cin >> n >> q;
std::vector<int> a(n + 1);
for(int i = 1; i <= n; i++) {
std::cin >> a[i];
}
std::vector<int> last(n + 1);
std::map<int,int> lst;
for(int i = 1; i <= n; i++) {
last[i] = lst[a[i]];
lst[a[i]] = i;
}
lst.clear();
std::vector<int> next(n + 1, n + 1);
for(int i = n; i >= 1; i--) {
if(lst[a[i]]) {
next[i] = lst[a[i]];
}
lst[a[i]] = i;
}
while(q--) {
int l, r;
std::cin >> l >> r;
int ans = 0;
std::map<int, int> was;
for(int i = r; i >= l; i--) {
if(was[a[i]]) {
continue;
}
was[a[i]] = 1;
if(next[i] > r && last[last[i]] < l && last[i] >= l) {
ans += 1;
}
}
std::cout << ans << "\n";
}
}
signed main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int t = 1;
//std::cin >> t;
while (t--) {
solve();
}
return 0;
}
