#include <iostream>
#include <map>
#include <algorithm>
#include <cmath>
using namespace std;
using namespace std;
const int N = 5e5 + 5;
int block = 0;
int a[N], ans[N], finalans[N];
int currans = 0;
long long cnt[N];
struct query
{
int l, r, ind;
};
query queries[N];
bool cmp(query q1, query q2)
{
long long block1 = q1.l / block;
long long block2 = q2.l / block;
if (block1 != block2)
{
return block1 < block2;
}
else if (q1.r != q2.r)
{
return q1.r < q2.r;
}
else
return q1.ind < q2.ind;
}
void add(int i)
{
cnt[a[i]]++;
if (cnt[a[i]] == 2)
{
currans++;
}
else if (cnt[a[i]]==3)
{
--currans;
}
}
void del(int i)
{
cnt[a[i]]--;
if (cnt[a[i]]==1)
{
--currans;
}
if (cnt[a[i]] == 2)
{
++currans;
}
}
long long move(int l1, int r1, int l2, int r2)
{
while (r1 < r2)
{
++r1;
add(r1);
}
while (l1 > l2)
{
--l1;
add(l1);
}
while (l1 < l2)
{
del(l1);
++l1;
}
while (r1 > r2)
{
del(r1);
--r1;
}
return currans;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n,q;
cin >> n >> q;
block = (n/(int)sqrt(q));
for (int i = 0;i < n;++i)
{
cin >> a[i];
}
for (int i = 0;i < q;++i)
{
int l, r;
cin >> l >> r;
--l;
--r;
queries[i].l = l;
queries[i].r = r;
queries[i].ind = i;
}
sort(queries, queries + q, cmp);
int l0 = queries[0].l;
int r0 = queries[0].r;
for (int i = l0;i <= r0;++i)
{
cnt[a[i]]++;
if (cnt[a[i]] == 3)
--currans;
else if (cnt[a[i]] == 2)
++currans;
}
ans[0] = currans;
for (int i = 1;i < q;++i)
{
int l1 = queries[i-1].l;
int r1 = queries[i-1].r;
int l2 = queries[i].l;
int r2 = queries[i].r;
ans[i]=move(l1, r1, l2, r2);
}
for (int i = 0;i < q;++i)
{
finalans[queries[i].ind] = ans[i];
}
for (int i = 0;i < q;++i)
{
cout << finalans[i] << endl;
}
}
