JOI 商店出售 $N$ 件商品，编号从 $0$ 到 $N-1$。编号为 $i$（$0 \le i \le N-1$）的商品价格为 $P_i$。任意两件商品的价格互不相同。

Anna 来到 JOI 商店购物。在编号位于 $L$ 到 $R$（含端点）之间的商品中，Anna 想要购买价格最低的一件。由于 Anna 不知道每件商品的价格，她将与 JOI 商店的店员 Bruno 通信来决定购买哪一件商品。Bruno 知道每件商品的价格，但他不知道 $L$ 和 $R$ 的值。

Anna 和 Bruno 将使用一台通信设备发送字符。他们发送的每个字符都是 0 或 1。Anna 最多可以向 Bruno 发送 18 个字符，而 Bruno 最多可以向 Anna 发送 10 000 个字符。Bruno 希望发送尽可能少的字符。

$N, L, R$ 的值将提供给 Anna，而 $N$ 以及每件商品的价格将提供给 Bruno。请编写程序，实现 Anna 的策略和 Bruno 的策略，使得 Anna 能够决定要购买哪一件商品。

实现细节

你需要提交两个文件。

Anna.cpp

第一个文件是 Anna.cpp，用于实现 Anna 的策略。程序需要使用预处理指令 #include 引入 Anna.h，并实现以下函数。

• void InitA(int N, int L, int R)

  对于每个测试用例，该函数在开始时恰好被调用一次。

  • 参数 $N$ 表示商品数量 $N$。
  • 参数 $L$ 和 $R$ 表示 Anna 想要在编号介于 $L$ 和 $R$（含端点）之间的商品中购买最便宜的一件。

• void ReceiveA(bool x)

  每当 Bruno 向 Anna 发送一个字符时，该函数就会被调用一次。

  • 参数 $x$ 表示 Bruno 发送给 Anna 的字符，其中 true 表示字符 1，false 表示字符 0。

• int Answer()

  当所有调用结束后，该函数恰好被调用一次。该函数应返回 Anna 将要购买的商品的编号。

  • 返回值应是一个介于 $L$ 和 $R$（含端点）之间的整数。如果不满足该条件，你的程序将被判为 Wrong Answer [1]。
  • 如果返回值与 Anna 实际应购买的商品不同，你的程序将被判为 Wrong Answer [2]。

在该文件中，你的程序可以调用以下函数。

• void SendA(bool y)

  Anna 可以通过该函数向 Bruno 发送一个字符。

  • 参数 $y$ 表示 Anna 发送给 Bruno 的字符，其中 true 表示字符 1，false 表示字符 0。

Bruno.cpp

第二个文件是 Bruno.cpp，用于实现 Bruno 的策略。程序需要使用预处理指令 #include 引入 Bruno.h，并实现以下函数。

• void InitB(int N, std::vector<int> P)

  对于每个测试用例，该函数在开始时恰好被调用一次。

  • 参数 $N$ 表示商品数量 $N$。
  • 参数 $P$ 是一个长度为 $N$ 的数组，表示 $P[i]$ 是编号为 $i$（$0 \le i \le N-1$）的商品的价格 $P_i$。

• void ReceiveB(bool y)

  每当 Anna 向 Bruno 发送一个字符时，该函数就会被调用一次。

  • 参数 $y$ 表示 Anna 发送给 Bruno 的字符，其中 true 表示字符 1，false 表示字符 0。

在该文件中，你的程序可以调用以下函数。

• void SendB(bool x)

  Bruno 可以通过该函数向 Anna 发送一个字符。

  • 参数 $x$ 表示 Bruno 发送给 Anna 的字符，其中 true 表示字符 1，false 表示字符 0。

程序执行方式

你可以假设程序将按如下方式执行。对于每个测试用例，准备两个队列：$Q_Y$ 用于存放 Anna 发送的字符，$Q_X$ 用于存放 Bruno 发送的字符。开始时，会调用 InitA 和 InitB，并将这些函数中发送的字符压入对应的队列。随后重复以下过程：

• 如果 $Q_X$ 或 $Q_Y$ 中至少有一个非空，则从其中一个队列中取出一个字符，并调用相应的 ReceiveA 或 ReceiveB。如果 $Q_X$ 和 $Q_Y$ 都非空，则不确定会调用 ReceiveA 还是 ReceiveB。
• 每当在执行 ReceiveA 的过程中调用 SendA，发送的字符会被压入 $Q_Y$。
• 每当在执行 ReceiveB 的过程中调用 SendB，发送的字符会被压入 $Q_X$。
• 如果两个队列都为空，则调用 Answer，程序终止。

Anna 向 Bruno 发送的字符数不得超过 18 个，否则程序将被判为 Wrong Answer [3]。Bruno 向 Anna 发送的字符数不得超过 10 000 个，否则程序将被判为 Wrong Answer [4]。

重要说明

• 你的程序可以实现其他内部使用的函数，或使用全局变量。提交的文件将与评测程序一起编译，成为一个可执行文件。所有全局变量和内部函数都应声明在匿名命名空间中，以避免与其他文件发生冲突。评测时，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 L R
P0 P1 ··· P_{N-1}

输出格式（示例评测器）

当程序成功结束时，示例评测器会向标准输出写入以下信息（为清晰起见加上引号）：

• 如果答案正确，输出 Anna 发送给 Bruno 的字符总数 $Y$，以及 Bruno 发送给 Anna 的字符总数 $X$，格式为 "Accepted: Y X"。
• 如果程序被判为 Wrong Answer，则输出其类型，例如 "Wrong Answer [1]"。

如果程序同时满足多种 Wrong Answer 条件，示例评测器只会报告其中一种。

限制

• $1 \le N \le 1\,000\,000$。
• $0 \le L \le R \le N-1$。
• $1 \le P_i \le N$（$0 \le i \le N-1$）。
• $P_i \ne P_j$（$0 \le i < j \le N-1$）。

子任务

1. （1 分）$N \le 1\,000$。
2. （9 分）$N \le 10\,000$。

3. （90 分）无额外限制。

4. 设 $T$ 为该子任务中，每个测试用例里 Bruno 向 Anna 发送字符数量的最大值。

5. 该子任务的得分计算方式如下：
   • 若 $5\,000 < T \le 10\,000$，得分为 $\left\lfloor 25 \times \dfrac{10000 - T}{5000} \right\rfloor$ 分。
   • 若 $1\,000 < T \le 5\,000$，得分为 $25 + \left\lfloor 40 \times \dfrac{5000 - T}{4000} \right\rfloor$ 分。
   • 若 $300 < T \le 1\,000$，得分为 $65 + \left\lfloor 25 \times \dfrac{1000 - T}{700} \right\rfloor$ 分。
   • 若 $T \le 300$，得分为 90 分。

这里 $\lfloor x \rfloor$ 表示不超过 $x$ 的最大整数。

样例数据

下面给出了示例评测器的一个样例输入及其对应的函数调用过程。

样例输入 1：

4 0 2
3 1 4 2

对应的函数调用：