#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
#include <unordered_map>
using namespace std;
typedef long long ll;
const bool debug = true;
#define ff first
#define ss second
#define all(X) (X).begin(), (X).end()
#define rall(X) (X).rbegin(), (X).rend()
const int N = 5e5 + 5;
const int mod = 1e9 + 7;
int s = 750;
unordered_map<int, int>id;
int mp[N];
struct Query
{
int l, r, ind;
}Q[N];
int a[N];
bool cmp(Query a, Query b)
{
int bl = a.l / s;
int br = b.l / s;
if (bl != br)
return bl < br;
if (bl & 1)return a.r < b.r;
return a.r > b.r;
}
int ans;
int answ[N];
void add(int ind)
{
if (mp[a[ind]] == 2)ans--;
mp[a[ind]]++;
if (mp[a[ind]] == 2)
ans++;
}
void del(int ind)
{
if (mp[a[ind]] == 2)ans--;
mp[a[ind]]--;
if (mp[a[ind]] == 2)ans++;
}
void solve()
{
int n, q;
cin >> n >> q;
for (int i = 1; i <= n; i++)
{
cin >> a[i];
}
for (int i = 1; i <= q; i++)
{
int l, r;
cin >> l >> r;
Q[i] = { l, r, i };
}
sort(Q + 1, Q + 1 + q, cmp);
set<int>st;
for (int i = 1; i <= n; i++)st.insert(a[i]);
int c = 1;
for (auto i : st)
id[i] = c, c++;
for (int i = 1; i <= n; i++)
a[i] = id[a[i]];
int l = 0, r = 0;
for (int i = 1; i <= q; i++)
{
while (l < Q[i].l)
{
del(l);
l++;
}
while (r >= Q[i].r)
{
del(r);
r--;
}
while (l > Q[i].l)
{
l--;
add(l);
}
while (r < Q[i].r)
{
r++;
add(r);
}
answ[Q[i].ind] = ::ans;
}
for (int i = 1; i <= q; i++)
{
cout << answ[i] << " ";
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int t = 1;
//cin >> t;
while (t--)
{
solve();
}
return 0;
}
