#include <bits/stdc++.h>
using namespace std;
using ii = pair<int, int>;
const int N = 5e5 + 5;
int n, q, a[N], res[N], pre[N];
vector<ii> query[N];
namespace bit{
int bit[N], cur[N];
void update(int i, int x){
if(!i) return;
int tmp = x - cur[i]; cur[i] = x;
for(; i <= n; i += i & -i) bit[i] += tmp;
}
int pref(int i){
int res = 0;
for(; i > 0; i -= i & -i) res += bit[i];
return res;
}
int get(int l, int r){ return pref(r) - pref(l - 1); }
}
int32_t main(){
cin.tie(0)->sync_with_stdio(0);
cin >> n >> q;
for(int i = 1; i <= n; i++) cin >> a[i];
for(int i = 1; i <= q; i++){
int l, r; cin >> l >> r;
query[r].push_back({l, i});
}
map<int, int> lst;
for(int i = 1; i <= n; i++){
pre[i] = lst[a[i]];
lst[a[i]] = i;
}
for(int i = 1; i <= n; i++){
bit::update(pre[i], 1);
bit::update(pre[pre[i]], -1);
bit::update(pre[pre[pre[i]]], 0);
for(auto [l, id] : query[i]) res[id] = bit::get(l, i);
}
for(int i = 1; i <= q; i++) cout << res[i] << "\n";
}
