AT_pakencamp_2019_day3_f クリスマス飾り2

在 AtCoder 王国中，最高的塔被称为「AtCoder Tower」。为迎接圣诞节，塔上直线排列着 $N$ 个装饰品。 这些装饰品共有 $N$ 种颜色，编号分别为色 $1$、色 $2$、色 $3$，一直到色 $N$。最初，从左到右第 $i$ 个装饰品的颜色是 $A_i$。 国王高桥君打算选择性地去掉一些装饰品，使剩下的装饰品排列显得「美观」。所谓「美观」需要满足以下两个条件： - 剩下的装饰品颜色种类不超过 $2$ 种。 - 不存在两个相邻装饰品的颜色相同的情况。 例如，如果处理后剩下的装饰品排列如\[A\] \[B\]所示，就算达到了「美观」。然而，如果排列如\[C\] \[D\]所示，则不算「美观」。 在未来的 $Q+1$ 天内，塔上的装饰品会有 $Q$ 次颜色变化：在第 $i$ 天的晚上，第 $X_i$ 个装饰品的颜色会被改为色 $Y_i$。 请在每个第 $i$ 天中午，回答如下问题： - 最少需要移除多少个装饰品，才能让排列达到「美观」状态？

输入按照以下格式给出： > $N$ $A_1$ $A_2$ $A_3$ ... $A_N$ $Q$ $X_1$ $Y_1$ $X_2$ $Y_2$ $X_3$ $Y_3$ ... $X_Q$ $Y_Q$

输出 $Q+1$ 行。 每行输出一个整数，第 $i$ 行表示在第 $i$ 天中午，达到「美观」状态须移除的最少装饰品数量。

- $1 \leq N \leq 3000$ - $0 \leq Q \leq 7000$ - $1 \leq X_i \leq N$ - $1 \leq Y_i \leq N$ - $1 \leq A_i \leq N$ - 所有输入值均为整数 ### 部分分值任务 题目被分为几个小任务，只有当代码通过该任务的所有测试才会获得分数。总分为所有通过任务分数的累加。 1. (2 分) $N = 1$，$Q = 0$。 2. (11 分) $N \leq 15$，$Q = 0$。 3. (12 分) $A_i \leq 2$，$Y_i \leq 2$。 4. (13 分) $N \leq 250$，$Q = 0$。 5. (18 分) $Q = 0$。 6. (44 分) 无额外限制。 对于第 6 小任务，得分如下： - 如果 $Q \leq 600$ 的测试用例全部通过，得 24 分。 - 如果 $Q \leq 1500$ 的测试用例全部通过，加 5 分。 - 如果 $Q \leq 2500$ 的测试用例全部通过，加 5 分。 - 如果 $Q \leq 4500$ 的测试用例全部通过，加 5 分。 - 如果全部测试用例都通过，再加 5 分。 ### 第三任务提示 在该任务中，无论哪一天，装饰品颜色仅为色 $1$ 和色 $2$。在这种情况下，满足「美观」的排列可以是从左到右交替排列为色 $1, 2, 1, \ldots$，或色 $2, 1, 2, \ldots$。 ### 示例解释 1 在此情况下，不需要移除任何装饰品就能达到「美观」状态，所以输出 $0$。 ### 示例解释 2 如下图所示，移除 $4$ 个装饰品后，可以达到「美观」状态。  该输入示例符合第二个小任务的约束条件。 ### 示例解释 3 由于 $Q=10$，因此需输出 $11$ 行结果。 **本翻译由 AI 自动生成**