F. CodeForces-1446D2 Frequency Problem (Hard Version) *3000
如果全局众数不唯一，则答案是 \(n\)。
可以发现一个性质：答案区间的众数一定包含全局众数。否则一定可以扩展这个区间直到全局众数成为区间众数，如果此时区间众数出现次数又增加了，那么可以继续扩展。
仔细思考这个性质，发现实际只要统计最长的区间使得存在某个数的出现次数大于等于全局众数出现次数即可，证明依旧套用上面的方法，如果是大于或者等于但不是区间众数，那么一定可以继续扩展。
于是得到 Easy Version 的 \(O(nV)\) 做法，枚举每个值 \(k\)，维护前缀中全局众数与 \(k\) 出现次数之差，每次找这个差第一次出现位置更新答案。
基于值域做法考虑根号分治，那么出现次数大于 \(B\) 的部分已经解决了。
考虑出现次数小于 \(B\) 的部分，结合上面的性质，我们要找的区间 \([l,r]\) 应当满足 \(l-1\) 和 \(r+1\) 超过范围或者是全局众数，因为这样的 \([l,r]\) 可以看作固定全局众数出现次数的极长区间，也就是其他数的出现次数尽可能大。结合出现次数小于 \(B\)，将每个不含全局众数的极长连续段看作整体，那么要找的区间只含 \(O(B)\) 个段。
考虑固定最左侧的段，暴力扫过每个段直到全局众数出现次数超过 \(B\)，每次求众数时枚举最右侧段的数与加入这个段之前的众数比较，这样每个段被暴力枚举当且仅当作为一个区间最右侧的段，那么时间复杂度就是 \(O(nB)\)。
非常纯净，直接 \(B=\sqrt{n}\)，时间复杂度 \(O(n\sqrt{n})\)。
