#include <bits/stdc++.h>
#define _CRT_SECURE_NO_WARNINGS
using namespace std;
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define uniq(x) x.resize(unique(all(x)) - x.begin());
#define sort_uniq(x) sort(all(x)), uniq(x);
#define ll long long
#define ld long double
#define pii pair<int, int>
#define pll pair<ll, ll>
#define V vector
#define V2dll V<V<ll>>
#define V2dint V<V<int>>
#define V2dchar V<V<char>>
#define V2dbool V<V<bool>>
#define V3dll V<V<V<ll>>>
#define V3dint V<V<V<int>>>
#define V3dchar V<V<V<char>>>
#define lb lower_bound
#define ub upper_bound
#define pb push_back
#define eb emplace_back
#define FASTIO \
ios_base::sync_with_stdio(false); \
cin.tie(nullptr); \
cout.tie(nullptr);
#define INF INT32_MAX
#define blt __builtin_popcount
#define clr(x) x.clear()
#define ff first
#define ss second
#define popf pop_front
#define popb pop_back
#define sz(x) int(x.size())
#define rep(a, b, c, d) for (int a = b; a <= c; a += d)
#define repl(a, b, c, d) for (int a = b; a >= c; a -= d)
int sign(int x) {
if (x < 0) return -1;
if (x == 0) return 0;
return 1;
}
struct query {
int l, r, id;
};
int main() {
FASTIO
int n, q; cin >> n >> q;
int sq = sqrt(n);
V<int> a(n + 1);
rep(i, 1, n, 1)
cin >> a[i];
V<query> qr;
int ttt = 1;
while(q--) {
int l, r; cin >> l >> r;
qr.pb({l, r, ttt}); ++ttt;
}
map<int, int> mp;
rep(i, 1, n, 1)
mp[a[i]] += 1;
int timer = 1;
for (auto [val, bs] : mp) {
//cout << val << " " << bs << endl;
mp[val] = timer; ++timer;
}
rep(i, 1, n, 1)
a[i] = mp[a[i]];
//rep(i, 1, n, 1)
// cout << a[i] << " ";
//cout << endl;
sort(all(qr), [&](query a, query b){
int l1 = a.l / sq;
int l2 = b.l / sq;
if (l1 != l2)
return l1 < l2;
else
return a.r < b.r;
});
V<int> cnt(n + 1, 0);
int cur = 0;
function<void(int, int)> pos_add = [&](int pos, int dir) {
//cout << pos << " " << dir << endl;
if (cnt[a[pos]] == 2)
--cur;
cnt[a[pos]] += dir;
if (cnt[a[pos]] == 2)
++cur;
};
int r = 0, l = 1;
V<int> ans(sz(qr) + 1);
rep(i, 0, sz(qr) - 1, 1) {
while (r != qr[i].r) {
int dir = -sign(r - qr[i].r);
r += dir;
pos_add(r, dir);
}
while (l != qr[i].l) {
int dir = -sign(l - qr[i].l);
l += dir;
pos_add(l, -dir);
}
///rep(i, 1, n, 1)
//cout << cnt[i] << " ";
ans[qr[i].id] = cur;
//cout << cur << " " << qr[i].id << endl;
}
rep(i, 1, sz(qr), 1)
cout << ans[i] << "\n";
}
