#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#define ll long long
#define ull unsigned long long
#define ld long double
#define pll pair<ll, ll>
#define pii pair<int, int>
#define coutpair(p) cout << p.first << " " << p.second << "|"
#define fi first
#define se second
template<class T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<class T> using ordered_multiset = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;
const int blk = 707;
bool cmp(pair<pii, int>&i, pair<pii, int>&j){
ll fblk = i.fi.fi/blk, sblk = j.fi.fi/blk;
if (fblk == sblk) return i.fi.second < j.fi.second;
else return fblk < sblk;
}
int n, q;
int a[500005], dis[500005], ans[500005];
int occ[500005];
int curans = 0;
void discr(){
vector<int> unq_v;
unq_v.reserve(n);
for (int i=1; i<=n; i++) unq_v.push_back(a[i]);
sort(unq_v.begin(), unq_v.end());
unq_v.erase(unique(unq_v.begin(), unq_v.end()), unq_v.end());
for (int i=1; i<=n; i++) dis[i] = lower_bound(unq_v.begin(), unq_v.end(), a[i])-unq_v.begin()+1;
}
inline void add(int x){
occ[dis[x]]++;
if (occ[dis[x]] == 2) curans++;
else if (occ[dis[x]] == 3) curans--;
}
inline void sub(int x){
occ[dis[x]]--;
if (occ[dis[x]] == 2) curans++;
else if (occ[dis[x]] == 1) curans--;
}
int l = 1, r = 0;
void advance(int ql, int qr){
while (r < qr) add(++r);
while (l > ql) add(--l);
while (l < ql) sub(l++);
while (r > qr) sub(r--);
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n >> q;
for (int i=1; i<=n; i++) cin >> a[i];
discr();
pair<pii, int> qry[q];
for (int i=0; i<q; i++) cin >> qry[i].fi.fi >> qry[i].fi.se, qry[i].se = i;
sort(qry, qry+q, cmp);
for (int i=0; i<q; i++){
auto [p, idx] = qry[i];
auto [ql, qr] = p;
advance(ql, qr);
ans[idx] = curans;
}
for (int i=0; i<q; i++) cout << ans[i] << "\n";
return 0;
}
