```
#include<bits/stdc++.h>
#define int long long
using namespace std;
struct node{
int l, r;
int id;
}que[2000100];
int arr[2000010];
int what[2000010];
int tempwhat[2000010];
int block;
bool cmp(node x, node y) {
if(x.l/block == y.l / block) {
return x.r < y.r;
}
return x.l / block < y.l / block;
}
int ans, anstime = 1;
void add(int index) {
tempwhat[what[arr[index]]]--;
what[arr[index]]++;
tempwhat[what[arr[index]]]++;
if(what[arr[index]] > ans) {
ans = what[arr[index]];
}
}
void del(int index) {
if(what[arr[index]] == ans && tempwhat[what[arr[index]]] == 1) {
ans--;
}
tempwhat[what[arr[index]]]--;
what[arr[index]]--;
tempwhat[what[arr[index]]]++;
}
int anss[2000100];
signed main() {
ios::sync_with_stdio(0); cin.tie(0);
int n, q;
cin >> n >> q;
for(int i=1; i<=n; ++i) {
cin >> arr[i];
que[i].id = i;
arr[i]+=100000;
}
block = sqrt(n);
for(int i=1; i<=q; ++i) {
cin >> que[i].l >> que[i].r;
}
sort(que+1, que+1+q, cmp);
int l = 1, r = 0;
for(int i=1; i<=q; ++i) {
while(r < que[i].r) {
r++;
add(r);
}
while(r > que[i].r) {
del(r);
r--;
}
while(l < que[i].l) {
del(l);
l++;
}
while(l > que[i].l) {
l--;
add(l);
}
anss[que[i].id] = ans;
}
for(int i=1; i<=q; ++i) {
cout << anss[i] << endl;
}
return 0;
}
```
by LonginusMonkey @ 2023-10-04 14:27:13