CF1446D2.Frequency Problem (Hard Version)

This is the hard version of the problem. The difference between the versions is in the constraints on the array elements. You can make hacks only if all versions of the problem are solved.

You are given an array $[a_1, a_2, \dots, a_n]$.

Your goal is to find the length of the longest subarray of this array such that the most frequent value in it is not unique. In other words, you are looking for a subarray such that if the most frequent value occurs $f$ times in this subarray, then at least $2$ different values should occur exactly $f$ times.

An array $c$ is a subarray of an array $d$ if $c$ can be obtained from $d$ by deletion of several (possibly, zero or all) elements from the beginning and several (possibly, zero or all) elements from the end.

这是该问题的困难版本。两个版本的区别在于对数组元素的约束条件不同。只有当该问题的所有版本均被解决后，才允许进行 hack。

给定一个数组 $[a_1, a_2, \dots, a_n]$。

你的目标是找出该数组中最长子数组的长度，使得该子数组中出现频率最高的值不唯一。换言之，你需寻找一个子数组：若其中最高频值的出现次数为 $f$，则至少有 2 个互不相同的值 在该子数组中恰好各出现 $f$ 次。

若数组 $c$ 可通过从数组 $d$ 的开头删除若干（可能为零或全部）元素、并从结尾删除若干（可能为零或全部）元素而得到，则称 $c$ 是 $d$ 的一个子数组。

The first line contains a single integer $n$ ($1 \le n \le 200\,000$) — the length of the array.

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le n$) — elements of the array.

第一行包含一个整数 $n$（$1 \le n \le 200\,000$）—— 数组的长度。

第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \le a_i \le n$）—— 数组的元素。

You should output exactly one integer — the length of the longest subarray of the array whose most frequent value is not unique. If there is no such subarray, output $0$.

你应该输出一个整数——该数组中满足“出现频率最高的值不唯一”的最长子数组的长度。如果不存在这样的子数组，则输出 $0$。

In the first sample, the subarray $[1, 1, 2, 2, 3, 3]$ is good, but $[1, 1, 2, 2, 3, 3, 3]$ isn't: in the latter there are $3$ occurrences of number $3$, and no other element appears $3$ times.

在第一个样例中，子数组 $[1, 1, 2, 2, 3, 3]$ 是“好”的，但 $[1, 1, 2, 2, 3, 3, 3]$ 不是：在后者中，数字 $3$ 出现了 $3$ 次，而没有其他元素出现 $3$ 次。