CF1163B2.Cat Party (Hard Edition)

This problem is same as the previous one, but has larger constraints.

Shiro's just moved to the new house. She wants to invite all friends of her to the house so they can play monopoly. However, her house is too small, so she can only invite one friend at a time.

For each of the $n$ days since the day Shiro moved to the new house, there will be exactly one cat coming to the Shiro's house. The cat coming in the $i$-th day has a ribbon with color $u_i$. Shiro wants to know the largest number $x$, such that if we consider the streak of the first $x$ days, it is possible to remove exactly one day from this streak so that every ribbon color that has appeared among the remaining $x - 1$ will have the same number of occurrences.

For example, consider the following sequence of $u_i$: $[2, 2, 1, 1, 5, 4, 4, 5]$. Then $x = 7$ makes a streak, since if we remove the leftmost $u_i = 5$, each ribbon color will appear exactly twice in the prefix of $x - 1$ days. Note that $x = 8$ doesn't form a streak, since you must remove exactly one day.

Since Shiro is just a cat, she is not very good at counting and needs your help finding the longest streak.

本题与上一题相同，但约束条件更大。

Shiro 刚刚搬进新家。她想邀请自己所有的朋友来家里玩大富翁游戏。然而，她的房子太小了，每次只能邀请一位朋友。

在 Shiro 搬入新家后的 $n$ 天中，每天恰好有一只猫来到 Shiro 家。第 $i$ 天到来的猫所佩戴的丝带颜色为 $u_i$。Shiro 想知道最大的整数 $x$，使得：若考虑前 $x$ 天构成的连续区间（即前缀），则存在恰好移除其中一天的方式，使得剩余 $x - 1$ 天中所有出现过的丝带颜色的出现次数均相等。

例如，考虑如下 $u_i$ 序列：$[2, 2, 1, 1, 5, 4, 4, 5]$。此时 $x = 7$ 是一个合法的连续区间，因为若移除最左边的 $u_i = 5$（即第 5 天），则前 $x - 1 = 6$ 天中每种出现的颜色均恰好出现两次。注意 $x = 8$ 不构成合法连续区间，因为你必须恰好移除一天。

由于 Shiro 只是一只猫，不擅长计数，因此需要你帮她找出最长的满足条件的连续区间长度。

The first line contains a single integer $n$ ($1 \leq n \leq 10^5$) — the total number of days.

The second line contains $n$ integers $u_1, u_2, \ldots, u_n$ ($1 \leq u_i \leq 10^5$) — the colors of the ribbons the cats wear.

第一行包含一个整数 $n$（$1 \leq n \leq 10^5$）—— 总天数。

第二行包含 $n$ 个整数 $u_1, u_2, \ldots, u_n$（$1 \leq u_i \leq 10^5$）—— 猫咪所佩戴丝带的颜色。

Print a single integer $x$ — the largest possible streak of days.

输出一个整数 $x$ —— 最长可能的连续天数。

In the first example, we can choose the longest streak of $13$ days, since upon removing the last day out of the streak, all of the remaining colors $1$, $2$, $3$, and $4$ will have the same number of occurrences of $3$. Note that the streak can also be $10$ days (by removing the $10$-th day from this streak) but we are interested in the longest streak.

In the fourth example, if we take the streak of the first $6$ days, we can remove the third day from this streak then all of the remaining colors $1$, $2$, $3$, $4$ and $5$ will occur exactly once.

在第一个例子中，我们可以选择最长的连续 $13$ 天，因为从此连续段中移除最后一天后，其余颜色 $1$、$2$、$3$ 和 $4$ 的出现次数均为 $3$。注意，该连续段也可以是 $10$ 天（通过从此连续段中移除第 $10$ 天），但我们关注的是最长的连续段。

在第四个例子中，若取前 $6$ 天构成的连续段，则可从此连续段中移除第 $3$ 天，使得其余颜色 $1$、$2$、$3$、$4$ 和 $5$ 均恰好出现一次。