#include<bits/stdc++.h>
#define fi first
#define se second
#define ll long long
#define ull unsigned long long
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define sz(x) (int) (x).size()
#define MASK(n) (1 << (n))
#define BIT(mask,x) ((mask << (x)) & 1)
#define TASK "task"
using namespace std;
const int mxN = 5e5 + 7;
const int base = 512;
const int Log = sqrt(mxN);
const int inf = 1e9 + 6969;
const int Mod = 1e9 + 7;
const long long infll = 1e18 + 6969;
template <typename T1, typename T2> bool minimize(T1 &a, T2 b) {
if (a > b) {a = b; return true;} return false;
}
template <typename T1, typename T2> bool maximize(T1 &a, T2 b) {
if (a < b) {a = b; return true;} return false;
}
struct item {
int l;
int r;
int idx;
bool operator < (const item & x) {
if(l / Log == x.l / Log) return r < x.r;
else return l / Log < x.l / Log;
}
}q[mxN];
int n;
int queries;
int a[mxN];
int res[mxN];
map<int,int>cnt;
void solve() {
cin >> n >> queries;
for (int i = 1; i <= n; i++) cin >> a[i];
for (int i = 1; i <= n; i++) cin >> q[i].l >> q[i].r,q[i].idx = i;
sort(q + 1,q + queries + 1);
int l = q[1].l,r = q[1].r,ans = 0;
for (int i = q[1].l; i <= q[1].r; i++) {
cnt[a[i]]++;
if(cnt[a[i]] == 2) ans++;
if(cnt[a[i]] == 3) ans--;
}
res[q[1].idx] = ans;
for (int i = 2; i <= queries; i++) {
while(l > q[i].l) {
l--;
if(cnt[a[l]] == 2) ans--;
cnt[a[l]]++;
if(cnt[a[l]] == 2) ans++;
}
while(l < q[i].l) {
l++;
if(cnt[a[l]] == 2) ans--;
cnt[a[l]]--;
if(cnt[a[l]] == 2) ans++;
}
while(r < q[i].r) {
r++;
if(cnt[a[r]] == 2) ans--;
cnt[a[r]]++;
if(cnt[a[r]] == 2) ans++;
}
while(r > q[i].r) {
r--;
if(cnt[a[r]] == 2) ans--;
cnt[a[r]]--;
if(cnt[a[r]] == 2) ans++;
}
res[q[i].idx] = ans;
}
for (int i = 1; i <= queries; i++) cout << res[i] << "\n";
}
signed main() {
ios_base :: sync_with_stdio(0);
cin.tie(0);
int tc = 1;
//cin >> tc;
while(tc--) {
solve();
}
}
