AT_otemae2019_c.カード並べ 2 (Arranging Card 2)

ピ太郎拥有两套各包含 $N$ 张卡片的卡片组。第一组称为 $A$，卡片上依次写有数 $a_1$ 到 $a_N$；第二组称为 $B$，卡片上依次写有数 $b_1$ 到 $b_N$。

ピ太郎可以随时按自己的喜好多次重新排列卡片组 $B$。

接下来，ピ太郎将进行 $N$ 次游戏，每次游戏的规则如下：

• 在第 $i$ ($1 \leq i \leq N$) 次游戏中，定义数列 $C_i$ 为卡片组 $A$ 的前 $i$ 张卡片所组成的数列。
• 你需要重新排列卡片组 $B$，使得数列 $C_i$ 在重新排列后的卡片组 $B$ 所组成的序列中非重叠地出现次数最多。
• 注意，数列 $C_i$ 的位置不能重叠。例如，数列 {1 2 1 2 1 2 1 2} 可以表示为 {(1 2 1 2) (1 2 1 2)}，其中数列 {1 2 1 2} 出现了 $2$ 次，不能将其视作其以任何重叠形式（如 {(1 2 1 2) 1 2 1 2} 或 {1 2 (1 2 1 2) 1 2} 等）出现 $3$ 次。
• 你需要输出数列 $C_i$ 在排列后的卡片组 $B$ 中的最大不重叠出现次数，也就是游戏得分。

请编写程序，计算并输出每场游戏中ピ太郎能够获得的最高得分。

从标准输入按以下格式读取输入：

$N$ $a_1$ $a_2$ $\cdots$ $a_N$ $b_1$ $b_2$ $\cdots$ $b_N$

输出 $N$ 行。第 $i$ ($1 \leq i \leq N$) 行表示第 $i$ 次游戏中ピ太郎能获得的最高得分。

约束条件

• 所有输入均为整数。
• $2 \leq N \leq 100\,000$。
• $1 \leq a_i, b_i \leq 100\,000$ ($1 \leq i \leq N$)。

子任务

1. （16 分）$N \leq 8$。
2. （10 分）$a_i = 1$ ($1 \leq i \leq N$)。
3. （24 分）$N \leq 1\,000$。
4. （50 分）无其他限制条件。

本翻译由 AI 自动生成