#include<bits/stdc++.h>
#define s second
#define f first
#define P pair<pair<int, int>, int>
using namespace std;
using ll = long long;
int sz;
bool cmp(P a, P b) {
if(a.f.f / sz == b.f.f / sz) {
if((a.f.f / sz) % 2 == 0) return (a.f.s < b.f.s);
else return (a.f.s > b.f.s);
} return (a.f.f < b.f.f);
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int n, q;
cin >> n >> q;
sz = sqrt(n) + 1;
int a[n];
for(int i = 0; i < n; i++) {
cin >> a[i];
}
vector<P> v;
for(int i = 0; i < q; i++) {
int x, y;
cin >> x >> y;
x--, y--;
v.push_back({{x, y}, i});
}
sort(v.begin(), v.end(), cmp);
int L = 0, R = 0;
int b[q];
map<ll, int> c;
int cnt = 0;
c[a[0]] = 1;
for(P p : v) {
int l = p.f.f;
int r = p.f.s;
int id = p.s;
while(R < r) {
R++;
c[a[R]]++;
if(c[a[R]] == 2) cnt++;
if(c[a[R]] == 3) cnt--;
}
while(L > l) {
L--;
c[a[L]]++;
if(c[a[L]] == 2) cnt++;
if(c[a[L]] == 3) cnt--;
}
while(L < l) {
c[a[L]]--;
if(c[a[L]] == 1) cnt--;
if(c[a[L]] == 2) cnt++;
L++;
}
while(R > r) {
c[a[R]]--;
if(c[a[R]] == 1) cnt--;
if(c[a[R]] == 2) cnt++;
R--;
}
b[id] = cnt;
}
for(int i = 0; i < q; i++) {
cout << b[i] << '\n';
}
return 0;
}
