#include <bits/stdc++.h>
#define debug(x) cout << #x << " = " << x << '\n'
#define int long long
#define pii pair<int, int>
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define ALL(x) x.begin(), x.end()
#define MASK(i) (1ll << (i))
#define FOR(i,a,b) for (int i = (a); i <= (b); ++i)
#define REV(i,a,b) for (int i = (a); i >= (b); --i)
using namespace std;
int n, q;
#define MAXN 500005
int a[MAXN];
struct query{
int l,r,i;
};
int SIZE = 707;
vector<query> Q;
int bid(int id){
return id / SIZE;
}
int res[MAXN];
int cnt[MAXN];
int ANS = 0;
void compress(){
vector<int> nenso;
FOR(i,0,n-1) nenso.pb(a[i]);
sort(ALL(nenso));
int cur = nenso[0];
int cnt = 1;
map<int,int>mp;
for (int &x : nenso){
if (cur != x) cur = x, cnt++;
mp[cur] = cnt;
}
FOR(i,0,n-1) a[i] = mp[a[i]];
}
void inc(int x){
if (cnt[x] == 2) ANS--;
if (cnt[x] == 1) ANS++;
cnt[x]++;
}
void dec(int x){
if (cnt[x] == 2) ANS--;
if (cnt[x] == 3) ANS++;
cnt[x]--;
}
void solve(){
cin >> n >> q;
FOR(i,0,n-1) cin >> a[i];
compress();
FOR(i,1,q){
int x,y; cin >> x >> y;
x--; y--;
Q.push_back({x,y,i});
}
sort(ALL(Q),[](const query&A, const query&B){
if (bid(A.l) != bid(B.l)) return bid(A.l) < (B.l);
return bid(A.l) & 1 ? A.r < B.r : A.r > B.r;
});
int ll = Q[0].l;
int rr = Q[0].r;
FOR(i,ll,rr){
inc(a[i]);
}
res[Q[0].i] = ANS;
FOR(i,1,q-1){
while (ll > Q[i].l) ll--, inc(a[ll]);
while (ll < Q[i].l) dec(a[ll]), ll++;
while (rr > Q[i].r) dec(a[rr]), rr--;
while (rr < Q[i].r) rr++, inc(a[rr]);
res[Q[i].i] = ANS;
}
FOR(i,1,q){
cout << res[i] << '\n';
}
}
int32_t main(){
ios_base::sync_with_stdio(false);
cin.tie(__null); cout.tie(__null);
solve();
return 0;
}
