← 返回题目列表

Codeforces · 1163/B2

B2. 猫派对(硬版)

中文机器翻译题面 查看原题

这个问题和上一个问题一样,但是有更大的约束。

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$$$,每个色带颜色将在 $$$x - 1$$$ 天的前缀中恰好出现两次。请注意,$$$x = 8$$$ 不会形成条纹,因为您必须恰好删除一天。

由于小白只是一只猫,她不太擅长数数,需要你的帮助找到最长的条纹。

输入

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

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

输出

打印单个整数 $$$x$$$ — 最大可能的天数。

示例

输入 #1

13
1 1 1 2 2 2 3 3 3 4 4 4 5

输出 #1

13

输入 #2

5
10 100 20 200 1

输出 #2

5

输入 #3

1
100000

输出 #3

1

输入#4

7
3 2 1 1 4 5 1

输出#4

6

输入 #5

6
1 1 1 2 2 2

输出 #5

5

注意

在第一个示例中,我们可以选择 $$$13$$$ 天的最长连续,因为从连续中删除最后一天后,所有剩余颜色 $$$1$$$、$$$2$$$、$$$3$$$ 和 $$$4$$$ 将具有相同的 $$$3$$$ 出现次数。请注意,连续记录也可以是 $$$10$$$ 天(通过从此连续记录中删除第 $$$10$$$ 天),但我们感兴趣的是最长的连续记录。

在第四个示例中,如果我们采用前 $$$6$$$ 天的连续,我们可以从该连续中删除第三天,然后所有剩余颜色 $$$1$$$、$$$2$$$、$$$3$$$、$$$4$$$ 和 $$$5$$$ 将恰好出现一次。