考虑对于每个数的出现次数根号分治。

• 若出现次数 $\ge \sqrt{n}$，这样的数不会超过 $\sqrt{n}$ 个。对每个数前缀和作差更新询问答案即可。

• 若出现次数 $< \sqrt{n}$，答案会比较小。定义 $f_{l, k}$ 表示最小的 $r$ 使得 $[l, r]$ 中存在一个数出现了至少 $k$ 次。

考虑 $f$ 怎么求。不难发现一个性质：$[l, f_{l, k}]$ 中一定有且只有一个数出现了恰好 $k$ 次。因为如果有数出现了 $>k$ 次或者是多于一个数出现了 $k$ 次都意味着有更小的 $r$，是矛盾的。

因此我们只要对每个 $k$ 双指针求一遍 $f$ 即可。这部分复杂度 $O(n \sqrt{n})$。

查询的时候，对于 $\ge \sqrt{n}$ 的部分前缀和作差，对于 $< \sqrt{n}$ 的部分从大到小枚举答案即可算出。$n, m$ 同阶，时间复杂度 $O(n\sqrt{n})$。

这个做法完全是可以在线的，但是在线做法空间稍大。因此我写了离线。

#include<bits/stdc++.h>
using namespace std;
int n, q, V, a[100005], f[405][100005], buk[100005], pre[100005], ans[100005], tbuk[100005];
struct que{
    int l, r;
}Q[100005];
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++){
        cin >> a[i];
        buk[a[i]]++;
        V = max(V, a[i]);
    }
    int B = sqrt(n);
    cin >> q;
    for (int i = 1; i <= q; i++)
        cin >> Q[i].l >> Q[i].r;
    for (int i = 1; i <= V; i++)
        if (buk[i] >= B){
            for (int j = 1; j <= n; j++)
                pre[j] = pre[j - 1] + (a[j] == i);
            for (int j = 1; j <= q; j++)
                ans[j] = max(ans[j], pre[Q[j].r] - pre[Q[j].l - 1]);
        }
    for (int i = 1; i <= n; i++)
        if (buk[a[i]] >= B)
            a[i] = -1;
    for (int val = 1; val < B; val++){
        int r = 0, jl = -1;
        for (int i = 1; i <= n; i++){
            while (r < n && jl == -1){
                ++r;
                if (a[r] == -1)
                    continue;
                tbuk[a[r]]++;
                if (tbuk[a[r]] == val){
                    jl = a[r];
                    break;
                }
            }
            if (r == n && jl == -1)
                f[val][i] = n + 1;
            else
                f[val][i] = r;
            if (a[i] == -1)
                continue;
            tbuk[a[i]]--;
            if (a[i] == jl)
                jl = -1;
        }
    }
    for (int i = 1; i <= q; i++){
        for (int j = B - 1; j; j--)
            if (f[j][Q[i].l] <= Q[i].r){
                ans[i] = max(ans[i], j);
                break;
            }
        cout << ans[i] << "\n";
    }
    return 0;
}