#include <bits/stdc++.h>
#define kien long long
#define FOR(i, a, b) for (int i = a;i <= b; i++)
#define FORD(i, a, b) for (int i = a;i >= b; i--)
#define task "a"
#define fin(x) freopen(x".inp","r",stdin)
#define fou(x) freopen(x".out","w",stdout)
#define pii pair <int, int>
#define pb push_back
using namespace std;
const int mxn = 5e5 + 5;
kien ans[mxn], n, a[mxn], lst[mxn], lst1[mxn], lst2[mxn];
kien l, r;
vector <pii> qr[mxn];
struct FenwickTree {
int N;
kien bit[mxn];
void init(int n) {
N = n;
for (int i = 1; i <= N; i++) bit[i] = 0;
}
void update(int pos, int val) {
for (; pos <= N; pos += pos & -pos) bit[pos] += val;
}
kien get(int pos) {
kien s = 0;
for (; pos > 0; pos -= pos & -pos) s += bit[pos];
return s;
}
void update_range(int u, int v, int val) {
update(u, val);
update(v + 1, -val);
}
} BIT;
//bool cmp (pii x, pii y) {
// return x.second < y.second;
//}
main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
if (fopen(task".inp", "r")) {
fin(task); fou(task);
}
kien q; cin >> n >> q;
vector <int> zip;
FOR (i, 1, n) {
cin >> a[i]; zip.pb(a[i]);
}
sort(zip.begin(), zip.end());
zip.erase(unique(zip.begin(), zip.end()), zip.end());
FOR (i, 1, n) a[i] = lower_bound(zip.begin(), zip.end(), a[i]) - zip.begin() + 1, lst[i] = lst1[i] = lst2[i] = 0;
BIT.init(n);
FOR (i, 1, q) { cin >> l >> r; qr[r].pb({l, i}); }
// sort (qr + 1, qr + 1 + q, cmp);
FOR (i, 1, n) {
int pre = lst[a[i]];
int pre1 = lst1[a[i]];
int pre2 = lst2[a[i]];
if (pre > 0) BIT.update_range(pre1 + 1, pre, 1);
if (pre1 > 0) BIT.update_range(pre2 + 1, pre1, -1);
// if (pre2 != -1) BIT.update_range(pre2 + 1, pre1, -1);
lst2[a[i]] = lst1[a[i]];
lst1[a[i]] = lst[a[i]];
lst[a[i]] = i;
for (auto x : qr[i]) {
ans[x.second] = BIT.get(x.first);
}
}
FOR (i, 1, q) cout << ans[i] << "\n";
}
