#include <bits/stdc++.h>
using namespace std;
#define all(a) begin(a), end(a)
const int N = 5e5 + 1, BLOCK = 800;
struct Query {
int l, r, i;
bool operator<(const Query& rhs) const {
if(l / BLOCK != rhs.l / BLOCK) return l < rhs.l;
return (l / BLOCK & 1) ? (r < rhs.r) : (r > rhs.r);
}
} quer[N];
int a[N], cnt[N], cnt1[N], res[N];
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int n, q; cin >> n >> q;
vector<int> compress;
for(int i = 1; i <= n; ++i) {
cin >> a[i];
compress.push_back(a[i]);
}
sort(all(compress));
compress.erase(unique(all(compress)), end(compress));
for(int i = 1; i <= n; ++i) a[i] = upper_bound(all(compress), a[i]) - begin(compress);
for(int i = 1; i <= q; ++i) {
cin >> quer[i].l >> quer[i].r;
quer[i].i = i;
}
sort(quer + 1, quer + q + 1);
int cur_l = 0, cur_r = -1;
for(int i = 1; i <= q; ++i) {
while(cur_l > quer[i].l) {
--cur_l;
--cnt1[cnt[a[cur_l]]];
++cnt1[++cnt[a[cur_l]]];
}
while(cur_r < quer[i].r) {
++cur_r;
--cnt1[cnt[a[cur_r]]];
++cnt1[++cnt[a[cur_r]]];
}
while(cur_l < quer[i].l) {
--cnt1[cnt[a[cur_l]]];
++cnt1[--cnt[a[cur_l]]];
++cur_l;
}
while(cur_r > quer[i].r) {
--cnt1[cnt[a[cur_r]]];
++cnt1[--cnt[a[cur_r]]];
--cur_r;
}
res[quer[i].i] = cnt1[2];
}
for(int i = 1; i <= q; ++i) cout << res[i] << endl;
}
