考古学家 Anna 和 Bruno 正在挖掘 IOI 王国的遗迹。在遗迹 A 中，Anna 发现了旧机器的布局。在遗迹 B 中，Bruno 发现了这台机器本身。
这台机器由 $N$ 个设备组成。这些设备排成一排，连接在一条电线上。设备共有三种类型，分别称为 X、Y 和 Z。从左到右，设备编号为 $0$ 到 $N - 1$。设备 $i$ ($0 \le i \le N - 1$) 的类型为 $S_i$。换句话说，$S_i$ 是 X、Y 或 Z 中的一种。
由于机器太大，Bruno 决定将设备逐个从机器上拆除。然而，由于设备之间通过电线相互作用，他必须非常小心拆除的顺序。关于从机器上拆除设备的方式，我们定义如下：
- 假设设备 $x, y, z$ ($0 \le x < y < z \le N - 1$) 尚未被拆除，且 $S_x = \text{X}, S_y = \text{Y}, S_z = \text{Z}$。此外，假设对于所有 $x < j < y$，设备 $j$ 已经被拆除；对于所有 $y < k < z$，设备 $k$ 已经被拆除。如果满足所有这些条件，并且我们拆除了设备 $y$，则称其为一次好拆除（good removal）。
- 任何其他拆除设备的方式都不是好拆除。
Bruno 必须拆除机器上的所有 $N$ 个设备，使得好拆除的次数尽可能多。然而，由于这三种类型的设备看起来很相似，他无法区分设备的类型。
由于 Anna 拥有机器的布局，她知道机器上每个设备的类型。因此，她将使用发射器来帮助 Bruno。使用发射器，她可以发送一个字符序列。她发送的每个字符要么是 $0$，要么是 $1$。
请编写一个程序，实现 Anna 的策略和 Bruno 的策略，使得好拆除的次数尽可能多。在本题中，如果 Anna 发送给 Bruno 的字符数越少，你将获得更高的分数。
实现细节
你需要提交两个文件。
第一个文件是 Anna.cpp。它应该实现 Anna 的策略。它应该实现以下函数。程序应使用预处理指令 #include 包含 Anna.h。
void Anna(int N, std::vector<char> S)对于每个测试用例，该函数在开始时被调用且仅被调用一次。- 参数 $N$ 是设备的总数。
- 参数 $S$ 是一个长度为 $N$ 的数组。这意味着 $S[i]$ 是设备 $i$ ($0 \le i \le N - 1$) 的类型。字符 $S[i]$ 为 ‘X’、‘Y’ 或 ‘Z’。
你的程序可以调用以下函数：
void Send(int a)使用此函数，Anna 向 Bruno 发送一个字符 $0$ 或 $1$。- 参数 $a$ 是发送给 Bruno 的信息，必须为 $0$ 或 $1$。如果不满足此条件，你的程序将被判为 Wrong Answer [1]。
Send函数的调用次数不得超过 $200\,000$ 次。如果超过 $200\,000$ 次，你的程序将被判为 Wrong Answer [2]。
第二个文件是 Bruno.cpp。它应该实现 Bruno 的策略。它应该实现以下函数。程序应使用预处理指令 #include 包含 Bruno.h。
void Bruno(int N, int L, std::vector<int> A)在Anna函数被调用后，该函数被调用且仅被调用一次。- 参数 $N$ 是设备的总数。
- 参数 $L$ 是 Anna 发送的字符（$0$ 或 $1$）的数量。
- 参数 $A$ 是一个长度为 $L$ 的数组。这意味着 Anna 按顺序发送了字符序列 $A[0], A[1], \dots, A[L-1]$ 给 Bruno。序列中的每个字符均为 $0$ 或 $1$。
你的程序可以调用以下函数：
void Remove(int d)使用此函数，你的程序回答如何拆除设备。- 参数 $d$ 是设备的索引，表示 Bruno 拆除了设备 $d$。
- 必须满足不等式 $0 \le d \le N - 1$。如果不满足此条件，你的程序将被判为 Wrong Answer [3]。
- 不允许使用相同的参数 $d$ 多次调用此函数。如果不满足此条件，你的程序将被判为 Wrong Answer [4]。
Remove函数必须被调用恰好 $N$ 次。当Bruno函数终止时，如果调用Remove函数的次数不等于 $N$，你的程序将被判为 Wrong Answer [5]。- 在所有 $N$ 个设备被拆除后，好拆除的次数应尽可能多。如果不满足此条件，你的程序将被判为 Wrong Answer [6]。
重要说明
- 你的程序可以实现其他内部函数或使用全局变量。提交的文件将与评测程序一起编译，并成为一个可执行文件。所有全局变量和内部函数都应在匿名命名空间中声明，以避免与其他文件冲突。在评测时，它将作为 Anna 和 Bruno 两个进程执行。Anna 的进程和 Bruno 的进程不能共享全局变量。
- 你的程序不得使用标准输入和标准输出。你的程序不得以任何方式与其他文件通信。但是，你的程序可以将调试信息输出到标准错误。
编译与测试运行
你可以从比赛网页下载包含示例评测程序的压缩包来测试你的程序。压缩包中还包含你的程序的示例源文件。
示例评测程序是 grader.cpp。为了测试你的程序，请将 grader.cpp、Anna.cpp、Bruno.cpp、Anna.h、Bruno.h 放在同一个目录下，并运行以下命令来编译你的程序：
g++ -std=gnu++17 -O2 -fsigned-char -o grader grader.cpp Anna.cpp Bruno.cpp
编译成功后，将生成可执行文件 grader。
注意，实际的评测程序与示例评测程序不同。示例评测程序将作为一个单一进程执行，它将从标准输入读取输入数据并将结果写入标准输出。
样例输入格式
示例评测程序从标准输入读取以下数据：
$N$ $S_0 \ S_1 \ \dots \ S_{N-1}$
其中 $S_i$ 和 $S_{i+1}$ ($0 \le i \le N - 2$) 由空格分隔。
数据范围
- $3 \le N \le 100\,000$。
- $S_i$ 为 X、Y 或 Z 中的一种 ($0 \le i \le N - 1$)。
子任务
- (5 分) $N \le 18$。
- (95 分) 无附加限制。在此子任务中，你的得分按以下方式计算：
- 令 $L$ 为该子任务中所有测试用例中调用
Send函数次数的最大值。 - 你的得分计算如下：
- 若 $160\,000 < L \le 200\,000$，得分为 $25 + \lfloor 10 \times \frac{200000 - L}{40000} \rfloor$ 分。
- 若 $100\,000 < L \le 160\,000$，得分为 $35 + \lfloor 30 \times \frac{160000 - L}{60000} \rfloor$ 分。
- 若 $70\,000 < L \le 100\,000$，得分为 $65 + \lfloor 30 \times (\frac{100000 - L}{30000})^2 \rfloor$ 分。
- 若 $L \le 70\,000$，得分为 $95$ 分。 这里 $\lfloor x \rfloor$ 是不超过 $x$ 的最大整数。
- 令 $L$ 为该子任务中所有测试用例中调用
样例
样例 1
输入：
4 X Y X Z
对应的函数调用：
| 调用 | 调用 |
|---|---|
Anna(4, {X, Y, X, Z}) |
Send(0) |
Send(1) |
|
Bruno(4, 2, {0, 1}) |
Remove(2) |
Remove(1) |
|
Remove(0) |
|
Remove(3) |
在这些示例函数调用中，4 个设备将按以下方式拆除：
- 开始时，4 个设备为 X Y X Z。
- Bruno 拆除设备 2。设备变为 X Y - Z。这里 - 表示该位置的设备已被拆除。
- Bruno 拆除设备 1。设备变为 X - - Z。由于 $(x, y, z) = (0, 1, 3)$ 满足条件，这是一次好拆除。
- Bruno 拆除设备 0。设备变为 - - - Z。
- 最后，Bruno 拆除设备 3。设备变为 - - - -。
好拆除的次数为 1。 在此样例输入中，好拆除的次数不可能大于 1。