CF1446D2 Frequency Problem (Hard Version)

这是该问题的困难版本。不同版本的区别在于数组元素的取值范围。只有在所有版本都被解决后，你才能进行 Hack。 给定一个数组 $[a_1, a_2, \dots, a_n]$。 你的目标是找到该数组中最长的子数组，使得该子数组中出现次数最多的值不是唯一的。换句话说，你需要找到一个子数组，若其中出现次数最多的值出现了 $f$ 次，则至少有 $2$ 个不同的值恰好出现了 $f$ 次。 如果数组 $c$ 是数组 $d$ 的一个子数组，则 $c$ 可以通过从 $d$ 的开头删除若干（可能为零或全部）元素和从结尾删除若干（可能为零或全部）元素得到。

第一行包含一个整数 $n$（$1 \le n \le 200\,000$），表示数组的长度。 第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \le a_i \le n$），表示数组的元素。

你需要输出一个整数，表示满足条件的最长子数组的长度。如果不存在这样的子数组，输出 $0$。

在第一个样例中，子数组 $[1, 1, 2, 2, 3, 3]$ 是合法的，但 $[1, 1, 2, 2, 3, 3, 3]$ 不是：在后者中，数字 $3$ 出现了 $3$ 次，没有其他元素出现 $3$ 次。 由 ChatGPT 4.1 翻译