#include <iostream>
#include <algorithm>
#include <map>
using namespace std;
const int BUCKET = 707;
const int N = 5e5;
int a[N + 1], sol[N + 1], f[N + 1];
int n, l = 1, r, ans, q;
struct ceva
{
int x, y, ind;
bool operator < (const ceva &a)const
{
if ((x / BUCKET) == (a.x / BUCKET))
return y < a.y;
return (x / BUCKET) < (a.x / BUCKET);
}
} query[N + 1];
void mo (int &l, int &r, int newl, int newr, int ind)
{
while (l < newl)
{
if (f[a[l]] == 2)
--ans;
f[a[l]]--;
if (f[a[l]] == 2)++ans;
l++;
}
while (l > newl)
{
l--;
if (f[a[l]] == 2)--ans;
f[a[l]]++;
if (f[a[l]] == 2)
++ans;
}
while (r > newr)
{
if (f[a[r]] == 2)
--ans;
f[a[r]]--;
if (f[a[r]] == 2)++ans;
--r;
}
while (r < newr)
{
++r;
if (f[a[r]] == 2)
--ans;
f[a[r]]++;
if (f[a[r]] == 2)
++ans;
}
sol[ind] = ans;
}
int main()
{
cin >> n >> q;
for (int i = 1; i <= n; ++i)
cin >> a[i];
for (int i = 1; i <= q; ++i)
cin >> query[i].x >> query[i].y, query[i].ind = i;
sort (query + 1, query + q + 1);
for (int i = 1; i <= q; ++i)
mo (l, r, query[i].x, query[i].y, query[i].ind);
for (int i = 1; i <= q; ++i)
cout << sol[i] << '\n';
return 0;
}
