Bajtazar 构思了一个 $1$ 到 $n$ 的排列 $P$。Bajtazar 希望你猜出数字 $1$ 在该排列中的位置。为了让你不必盲目猜测，Bajtazar 会回答以下形式的问题：
- $f(i, j, d)$：排列 $P$ 中第 $i$ 个元素与第 $j$ 个元素之差是否能被 $d$ 整除，即 $d \mid P[i] - P[j]$ 是否成立？
- $g(i, j)$：排列 $P$ 中第 $i$ 个元素是否大于第 $j$ 个元素？
在上述问题中，$i, j$ 是集合 $\{1, 2, \dots, n\}$ 中的任意下标，$d$ 是任意正整数。
在猜测过程中，你可以任意多次使用 $f$ 类问题，但 $g$ 类问题的提问次数必须尽可能少。
请编写一个与 Bajtazar 提供的库进行交互的程序来解决这个谜题。
评分
设 $M(n)$ 为在长度为 $n$ 的已知排列中找到数字 $1$ 所需的最少 $g$ 类问题次数（无论排列具体为何）。只有当你的程序执行的 $g$ 类问题次数不超过 $M(n)$ 时，才能在该测试点获得分数。此外，程序必须在时间限制内完成，因此需要执行合理数量的 $f$ 类问题（不一定是最少数量）。
在所有测试中，满足 $1 \le n \le 500\,000$。在占总分 $28\%$ 的测试中，满足额外条件 $n \le 5\,000$。
交互
要使用该库，请在程序开头包含：
- C/C++:
#include "cgdzlib.h" - Pascal:
uses pgdzlib;
该库提供以下函数和过程：
inicjuj– 返回数字 $n$。应在程序开始时调用且仅调用一次。- C/C++:
int inicjuj(); - Pascal:
function inicjuj: LongInt;
- C/C++:
f(i, j, d)– 向 Bajtazar 的库提出 $f$ 类问题。结果为一个数字：如果 $d \mid P[i] - P[j]$ 则返回 $1$，否则返回 $0$。- C/C++:
int f(int i, int j, int d); - Pascal:
function f(i, j, d : LongInt) : LongInt;
- C/C++:
g(i, j)– 向 Bajtazar 的库提出 $g$ 类问题。结果为一个数字：如果 $P[i] > P[j]$ 则返回 $1$，否则返回 $0$。- C/C++:
int g(int i, int j); - Pascal:
function g(i, j : LongInt) : LongInt;
- C/C++:
odpowiedz(k)– 告诉 Bajtazar 的库数字 $1$ 位于排列的第 $k$ 个位置（即 $P[k] = 1$）。调用此过程/函数将结束你的程序。- C/C++:
void odpowiedz(int k); - Pascal:
procedure odpowiedz(k : LongInt);
- C/C++:
你的程序不得读取任何数据（无论是从标准输入还是文件）。也不得向文件或标准输出写入任何内容。你可以向标准错误输出（stderr）写入信息，但请记住这会消耗宝贵的时间。
样例
下表展示了向 Bajtazar 的库提问以猜出 $1$ 所在位置的示例序列。
| Numer pytania | Wywołanie | Wynik | Wyjaśnienie |
|---|---|---|---|
inicjuj |
$5$ | $n = 5$ | |
| $1$ | f(1, 2, 2) |
$0$ | $2 \nmid P[1] - P[2]$ |
| $2$ | g(1, 2) |
$0$ | $P[1] < P[2]$ |
| $3$ | f(3, 2, 3) |
$1$ | $3 \mid P[3] - P[2]$ |
| $4$ | g(2, 5) |
$1$ | $P[2] > P[5]$ |
| $5$ | f(1, 3, 2) |
$1$ | $2 \mid P[1] - P[3]$ |
| $6$ | f(1, 4, 3) |
$1$ | $3 \mid P[1] - P[4]$ |
odpowiedz(4) |
回答 $k = 4$ |
说明
在第二个问题后，我们知道 $P[2] \neq 1$。因此在第三个问题后，存在以下可能性之一：$(P[2] = 2, P[3] = 5)$ 或 $(P[2] = 4, P[3] = 1)$，或 $(P[2] = 5, P[3] = 2)$。第四个问题排除了第一种可能性。第五个问题现在可以确定 $P[1] \in \{3, 4\}$。既然在第六个问题中我们有 $3 \mid P[1] - P[4]$，则 $P[1] = 4, P[4] = 1$。排列中寻找的位置为 $k = 4$。
上述问题序列正确地找到了 $1$ 的位置，但该测试点无法获得任何分数，因为对于任意五个元素的排列，找到 $1$ 最多只需要一个 $g$ 类问题（即 $M(5) = 1$）。注意，执行 $f$ 类问题的次数在此处不重要。
实现细节
在工作站的 /home/zawodnik/rozw/gdz 目录下提供了一个示例库，允许你测试解决方案的正确性。该库从标准输入读取排列描述，格式如下：
- 第一行包含整数 $n$ —— 排列长度；
- 第二行包含 $n$ 个由空格分隔的 $1$ 到 $n$ 的数字 —— 排列的各个元素。
库的示例输入位于文件 gdz0.in 中。程序结束后，库会在标准输出上打印你的解决方案给出的答案是否正确，以及提出的 $g$ 类问题的数量。
同一目录下包含使用该库的示例解决方案 gdz.c、gdz.cpp 和 gdz.pas。这些解决方案没有最小化 $g$ 类问题的数量。
编译解决方案与库的命令如下：
- C:
gcc -O2 -static cgdzlib.c gdz.c -lm -o gdz - C++:
g++ -O2 -static cgdzlib.c gdz.cpp -lm -o gdz - Pascal:
ppc386 -O2 -XS -Xt gdz.pas
解决方案文件和库应位于同一目录下。