说明

Anna 发明了一种神秘的二元运算 $\star$。对于小于等于 $1\,000\,000\,000$ 的非负整数 $x, y$，运算结果 $x \star y$ 也是一个小于等于 $1\,000\,000\,000$ 的非负整数。这个运算 $\star$ 是结合的。即，对于任意小于等于 $1\,000\,000\,000$ 的非负整数 $x, y, z$，等式 $(x \star y) \star z = x \star (y \star z)$ 恒成立。这个值可以简单地记作 $x \star y \star z$。

Anna 打算和 Bruno 玩一个游戏。她让 Bruno 来猜这个运算 $\star$。她首先向 Bruno 展示了 $N$ 个整数 $A_0, A_1, \dots, A_{N-1}$。然后，她向 Bruno 提出了若干个如下形式的询问：“$A_L \star A_{L+1} \star \cdots \star A_R$ 的值是多少？”

Bruno 说没有提示的话很难玩这个游戏。于是 Anna 决定给他一些提示。每次提示的过程如下：Bruno 选择两个数 $x, y$ 来询问 $x \star y$ 的值，Anna 则会告诉他 $x \star y$ 的结果。他可以在游戏开始时，也就是已知整数 $A_0, A_1, \dots, A_{N-1}$ 的情况下请求提示。他也可以在 Anna 向他提出某个询问时请求提示。当然，他希望尽量减少请求提示的次数。因为他希望表现得好像几乎知道关于运算 $\star$ 的一切，所以他尤其希望减少在收到询问之后请求提示的次数。

任务

编写一个程序，实现 Bruno 的策略，即通过请求提示来正确回答 Anna 的询问。

实现细节

你需要编写一个程序，实现请求提示并回答 Anna 询问的策略。你的程序必须通过 #include "secret.h" 包含头文件 secret.h。

你的程序需要实现以下过程。

• void Init(int N, int A[])

  该过程在程序开始时仅被调用一次。参数 $N$ 是 Anna 展示的整数的数量。参数 $A$ 是一个长度为 $N$ 的数组。元素 $A[0], A[1], \dots, A[N-1]$ 即为她展示的整数 $A_0, A_1, \dots, A_{N-1}$。

• int Query(int L, int R)

  当 Anna 向 Bruno 提出一个询问时，该过程被调用。这意味着她在询问 $A_L \star A_{L+1} \star \cdots \star A_R$ 的值（$0 \leq L \leq R \leq N - 1$）。

  该过程应返回 $A_L \star A_{L+1} \star \cdots \star A_R$ 的值。

你的程序中可以调用以下过程。

• int Secret(int X, int Y)

  当 Bruno 请求一个提示时，调用此过程。这意味着他在询问 $X \star Y$ 的值。参数 $X$ 和 $Y$ 必须是满足 $0 \leq X \leq 1\,000\,000\,000$ 和 $0 \leq Y \leq 1\,000\,000\,000$ 的整数。如果调用此过程时传入的参数不满足此条件，你的程序将被判定为 Wrong Answer [1] 并终止。

  该过程返回 $X \star Y$ 的值。

编译与测试运行

你可以从竞赛网页下载一个归档文件，其中包含一个用于测试你程序的样例评分器。该归档文件还包含一个你的程序的样例源文件。

样例评分器由一个源文件组成，文件名为 grader.c 或 grader.cpp。例如，如果你的程序是 secret.c 或 secret.cpp，你可以运行以下命令来编译你的程序。

• C

  gcc -O2 -std=c11 -o grader grader.c secret.c -lm
  

• C++

  g++ -O2 -std=c++11 -o grader grader.cpp secret.cpp
  

编译成功后，会生成可执行文件 grader。

请注意，实际评测使用的评分器与样例评分器不同。样例评分器将作为单个进程运行，它会从标准输入读取输入数据，并将结果写入标准输出。

样例评分器说明

样例评分器假设 Anna 的秘密二元运算 $\star$ 为 $x \star y = \min\left\{x + 2\left\lfloor \frac{y}{2} \right\rfloor, 1\,000\,000\,000\right\}$。这里 $\lfloor r \rfloor$ 表示不超过 $r$ 的最大整数。请注意，这与实际评分器的行为不同。

输入格式

样例评分器从标准输入读取以下数据。

• 第一行包含一个整数 $N$，表示 Anna 展示的整数的数量。
• 第二行包含 $N$ 个以空格分隔的整数 $A_0, A_1, \dots, A_{N-1}$，即 Anna 展示的整数。
• 第三行包含一个整数 $Q$，表示 Anna 提出的询问数量。
• 接下来的 $Q$ 行中，第 $(j+1)$ 行（$0 \leq j \leq Q - 1$）包含两个以空格分隔的整数 $L_j$ 和 $R_j$（$0 \leq L_j \leq R_j \leq N - 1$）。这表示在第 $(j+1)$ 个询问中，Anna 询问的是 $A_{L_j} \star A_{L_j+1} \star \cdots \star A_{R_j}$ 的值。

输出格式

程序成功终止后，样例评分器会将每次 Query 调用返回的值按行写入标准输出，每行一个。同时，它还会向标准错误输出以下信息。

• 如果你的程序被判定为 Wrong Answer [1]，它会输出 “Wrong Answer [1]”。（实际输出不含引号。）
• 如果你的程序未被判定为 Wrong Answer [1]，它会输出在过程 Init 中调用 Secret 的次数，以及在每次调用过程 Query 的过程中调用 Secret 的最大次数。

提示

样例交互

以下是样例评分器的一个样例输入，以及各过程之间交互的示例。注意，如果使用样例评分器，以下返回值是正确的。

输入
8
1 4 7 2 5 8 3 6
4
0 3
1 7
5 5
2 4

调用	返回值
Init(8, [1, 4, 7, 2, 5, 8, 3, 6])	无
Query(0, 3)	13
Query(1, 7)	32
Query(5, 5)	8
Query(2, 4)	13

在过程 Init 或过程 Query 中可以调用过程 Secret。例如，当调用 Secret(4, 7) 时，如果使用样例评分器，返回值将是 10，因为 $4 \star 7 = 10$。

第一次询问要求计算 $1 \star 4 \star 7 \star 2$ 的值。如果使用样例评分器，由于

$$1 \star 4 \star 7 \star 2 = (1 \star (4 \star 7)) \star 2 = (1 \star 10) \star 2 = 11 \star 2 = 13$$

成立，因此过程 Query 应返回 13。

约束条件

所有输入数据满足以下条件。

• $1 \leq N \leq 1000$。
• $0 \leq A_i \leq 1\,000\,000\,000$（$0 \leq i \leq N - 1$）。
• Query 的调用次数不超过 $10\,000$。

评分细则

如果对于每个测试点，你的程序都能成功运行结束，未被判定为 Wrong Answer [1]，并且每次调用 Query 时都返回了正确的结果，那么你的程序将获得相应的分数。

分数的计算方式如下：

(1) 如果对于每个测试点，都满足以下两个条件，则得分为 100：

• 在 Init 中，调用 Secret 的次数小于等于 8000。

• 在每次调用 Query 的过程中，调用 Secret 的次数小于等于 1。

(2) 如果你的程序不满足 (1)，但满足以下两个条件，则得分为 30：

• 在 Init 中，调用 Secret 的次数小于等于 8000。

• 在每次调用 Query 的过程中，调用 Secret 的次数小于等于 20。

(3) 如果你的程序不满足 (1) 或 (2)，则得分为 6。

翻译由 DeepSeek V3.2 完成