题目描述

题目译自 XX Olimpiada Informatyczna — III etap Gdzie jest jedynka?

Bajtazar 构思了一个从 $1$ 到 $n$ 的排列 $P$，并希望你猜出数字 $1$ 在排列中的位置。为了避免你盲目猜测，他会回答以下两种问题：

• $f(i, j, d)$：排列 $P$ 的第 $i$ 个元素与第 $j$ 个元素的差是否能被 $d$ 整除，即 $d \mid P[i] - P[j]$？
• $g(i, j)$：排列 $P$ 的第 $i$ 个元素是否大于第 $j$ 个元素？

其中，$i, j$ 为集合 $\{1, 2, \ldots, n\}$ 中的任意索引，$d$ 为任意正整数。

在猜谜游戏中，你可无限制使用 $f$ 类型问题，但需尽量减少 $g$ 类型问题的数量。请编写一个程序，与 Bajtazar 提供的库交互，解决这个谜题。

交互方式

程序需在开头引入库：

• C/C++: #include "cgdzlib.h"
• Pascal: uses pgdzlib;

库提供以下函数：

• inicjuj：返回 $n$，需在程序开始时调用一次。
  • C/C++: int inicjuj();
  • Pascal: function inicjuj: LongInt;
• f(i, j, d)：向库询问 $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;
• g(i, j)：向库询问 $g$ 类型问题，若 $P[i] > P[j]$ 返回 $1$，否则返回 $0$。
  • C/C++: int g(int i, int j);
  • Pascal: function g(i, j: LongInt): LongInt;
• odpowiedz(k)：告知库 $1$ 位于排列的第 $k$ 位（即 $P[k] = 1$），调用后程序终止。
  • C/C++: void odpowiedz(int k);
  • Pascal: procedure odpowiedz(k: LongInt);

你的程序不得读取任何数据（包括标准输入或文件），不得向文件或标准输出写入内容。可向标准错误输出（stderr）写入诊断信息，但这会消耗时间。

编译与运行

在「文件」中，提供示例库以测试程序的格式正确性。库从标准输入读取排列描述，格式如下：

• 第一行包含一个整数 $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

代码文件和库需位于同一目录。

样例

以下表格展示了一个与 Bajtazar 库交互的样例，成功找到 $1$ 的位置：

在第二个问题后，我们知道 $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$。因此，$1$ 位于位置 $k=4$。

此问题序列正确找到 $1$ 的位置，但不会得分，因为对于 $n=5$ 的任意排列，$M(5)=1$，而示例使用了两个 $g$ 类型问题。$f$ 类型问题数量不影响评分。

数据范围与提示

设 $M(n)$ 为在长度为 $n$ 的任意排列中找到 $1$ 的位置所需的最少 $g$ 类型问题数量。你的程序仅当使用的 $g$ 类型问题数量不超过 $M(n)$ 时，才能在该测试数据上得分。此外，程序需满足时间限制，因此 $f$ 类型问题的数量应合理（但无需最小化）。

对于 $28\%$ 的测试数据，$n \leq 5000$。
所有测试数据满足 $1 \leq n \leq 500000$。