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 自动生成**