#include <iostream>
#include <queue>
#include <vector>
#include <map>
#include <deque>
using namespace std;
int n = 0, q = 0, siz = 1;
vector <int> v;
map <pair <int, int>, int> ans;
map <int, vector <int> > queries;
vector <pair <int, int> > queries1;
map <int, deque <int> > inds;
vector <int> segtree;
vector <int> lazytree;
void apply_lazy (int u, int l, int r) {
segtree[u] += lazytree[u];
if (l != r) {
lazytree[2 * u] += lazytree[u];
lazytree[2 * u + 1] += lazytree[u];
}
lazytree[u] = 0;
}
void update_segtree (int L, int R, int K, int u, int l, int r) {
apply_lazy (u, l, r);
if (r < L || R < l)
return;
if (L <= l && r <= R) {
lazytree[u] = K;
apply_lazy (u, l, r);
return;
}
const int m = (l + r) / 2;
update_segtree (L, R, K, 2 * u, l, m);
update_segtree (L, R, K, 2 * u + 1, m + 1, r);
}
int get_segtree (int L, int R, int u, int l, int r) {
apply_lazy (u, l, r);
if (r < L || R < l)
return 0;
if (L <= l && r <= R)
return segtree[u];
const int m = (l + r) / 2;
return (
get_segtree (L, R, 2 * u, l, m) +
get_segtree (L, R, 2 * u + 1, m + 1, r)
);
}
int main () {
ios::sync_with_stdio (false);
cin.tie (0);
cout.tie (0);
cin >> n >> q;
while (siz < n)
siz *= 2;
segtree.resize (2 * siz);
lazytree.resize (2 * siz);
v.resize (n + 1);
for (int i = 1; i <= n; i++)
cin >> v[i];
for (int i = 1; i <= q; i++) {
int l = 0, r = 0;
cin >> l >> r;
queries[r].emplace_back (l);
queries1.emplace_back (l, r);
}
for (int i = 1; i <= n; i++) {
deque <int>& deq = inds[v[i]];
deq.emplace_back (i);
if (deq.size() == 2)
update_segtree (1, deq[0], 1, 1, 1, siz);
else if (deq.size() == 3) {
update_segtree (1, deq[0], -1, 1, 1, siz);
update_segtree (deq[0] + 1, deq[1], 1, 1, 1, siz);
} else if (deq.size() == 4) {
update_segtree (deq[0] + 1, deq[1], -1, 1, 1, siz);
update_segtree (deq[1] + 1, deq[2], 1, 1, 1, siz);
deq.pop_front ();
}
for (int& e : queries[i])
ans[{e, i}] = get_segtree (e, e, 1, 1, siz);
}
for (pair <int, int>& e : queries1)
cout << ans[e] << '\n';
}
