#include <stdio.h>
#include <string.h>
#define N 500000
#define Q 500000
unsigned int X = 12345;
int rand_() {
return (X *= 3) >> 1;
}
int *xx;
void sort(int *ii, int l, int r) {
while (l < r) {
int i = l, j = l, k = r, i_ = ii[l + rand_() % (r - l)], tmp;
while (j < k)
if (xx[ii[j]] == xx[i_])
j++;
else if (xx[ii[j]] < xx[i_]) {
tmp = ii[i], ii[i] = ii[j], ii[j] = tmp;
i++, j++;
} else {
k--;
tmp = ii[j], ii[j] = ii[k], ii[k] = tmp;
}
sort(ii, l, i);
l = k;
}
}
int ft[N];
void update(int i, int n, int x) {
while (i < n) {
ft[i] += x;
i |= i + 1;
}
}
int query(int i) {
int x = 0;
while (i >= 0) {
x += ft[i];
i &= i + 1, i--;
}
return x;
}
int main() {
static int aa[N], ii[N], ii1[N], ii2[N], ii3[N], ll[Q], rr[Q], hh[Q], ans[Q];
int n, q, h, i, a;
scanf("%d%d", &n, &q);
for (i = 0; i < n; i++) {
scanf("%d", &aa[i]);
ii[i] = i;
}
xx = aa, sort(ii, 0, n);
for (i = 0, a = 0; i < n; i++)
aa[ii[i]] = i + 1 == n || aa[ii[i + 1]] != aa[ii[i]] ? a++ : a;
for (h = 0; h < q; h++) {
scanf("%d%d", &ll[h], &rr[h]), ll[h]--, rr[h]--;
hh[h] = h;
}
xx = rr, sort(hh, 0, q);
memset(ii1, -1, n * sizeof *ii1), memset(ii2, -1, n * sizeof *ii2), memset(ii3, -1, n * sizeof *ii3);
for (i = 0, h = 0; i < n; i++) {
a = aa[i];
if (ii3[a] != -1)
update(ii3[a], n, 1);
if (ii2[a] != -1)
update(ii2[a], n, -2);
if (ii1[a] != -1)
update(ii1[a], n, 1);
ii3[a] = ii2[a], ii2[a] = ii1[a], ii1[a] = i;
while (h < q && rr[hh[h]] == i) {
int h_ = hh[h++];
ans[h_] = query(rr[h_]) - query(ll[h_] - 1);
}
}
for (h = 0; h < q; h++)
printf("%d\n", ans[h]);
return 0;
}
