#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;
map<int, int> cnt;
struct query
{
long long 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)
{
if (r2 >= r1)
{
for (int i = r1+1;i <= r2;++i)
{
add(i);
}
}
if (l2 <= l1)
{
for (int i = l1-1;i >= l2;--i)
{
add(i);
}
}
if (r2 < r1)
{
for (int i = r1;i > r2;--i)
{
del(i);
}
}
if (l2 > l1)
{
for (int i = l1;i <l2;++i)
{
del(i);
}
}
return currans;
}
int main()
{
int n,q;
cin >> n >> q;
block = (int)sqrt(n);
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);
long long l0 = queries[0].l;
long long r0 = queries[0].r;
for (int i = l0;i <= r0;++i)
{
cnt[a[i]]++;
if (cnt[a[i]] > 2)
--currans;
else if (cnt[a[i]] == 2)
++currans;
}
ans[0] = currans;
for (int i = 1;i < q;++i)
{
long long l1 = queries[i-1].l;
long long r1 = queries[i-1].r;
long long l2 = queries[i].l;
long long 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;
}
}
