看正解可以直接从算法四开始。

下文中记询问序列中三个数 $a_i,a_j,a_k$ 的结果为 $f(i,j,k)$。

算法一：

$2n$ 次询问。

考虑钦定两个数 $x,y$ 满足 $a_x < a_y$，并对非 $x,y$ 的其余下标 $i$ 都询问 $f(x,y,i)$。

只会存在以下几种情况：

• $a_i < a_x < a_y$，返回 $a_i + a_y$。
• $a_x < a_i < a_y$，返回 $a_x + a_y$。
• $a_x < a_y < a_i$，返回 $a_x + a_i$。

若 $|a_x - a_y| \ge 3$，则询问结果中会有一种值出现 $\ge 2$ 次，随后我们容易还原出 $\le a_x$ 和 $\ge a_y$ 的所有数字，这是平凡的。

若 $|a_x - a_y| \le 2$，则对于每个不同的 $a_x$，询问形成的序列都不同，我们也可以还原出 $\le a_x$ 和 $\ge a_y$ 的所有数字，这是不多赘述。

然后你发现如果 $a_x = 1, a_y = n$ 你就倒闭了，那咋办呢，可以考虑开局对四个数每三个都进行一次询问，去掉最小的数即可规避这种情况。

那么我们设 $a_x = c$，$a_y = d$，进行 $O(n)$ 次询问后进行以下分讨：

• 若 $c - 1 \ge 1$，则第二轮只需要钦定 $a_x = c - 1, a_y = c$ 即可。
• 若 $d + 1 \le n$，则第二轮只需要钦定 $a_x = d, a_y = d + 1$ 即可。

根据鸽笼原理，必定有一种情况被满足。

至于 $a_x > a_y$ 的做法同理。

因此我们可以在 $2n$ 次询问内做出这个题。

算法二：

$1.5 n$ 次询问。

引入一个新做法，考虑钦定两个数 $x,y$ 满足 $a_x < a_y$（$a_x > a_y$ 同理），且这两个数形成了一个支配区间 $[a_x,a_y]$。

依次对没有获得任何信息的 $i$ 询问 $q_i = f(x,y,i)$，若此时对 $i$ 询问得出的所有值中存在两个数 $k,l$ 满足 $q_k = q_l$，则一定会有以下两种情况之一：

• $a_x < a_k < a_l < a_y$。
• $a_x < a_l < a_k < a_y$。

那么此时 $k,l$ 形成了更小的支配区间，即支配区间 $[a_k,a_l]$ 的约束强于 $[a_x,a_y]$。

但是此时我们还是不能直接缩小这个支配区间，因为此时我们其实并不知道 $a_x,a_y$ 的值到底是多少，因此我们需要再询问一次 $f(x,k,l)$，这样我们之后就能确定出 $a_x,a_y$ 的值了，且此时我们不需要在意之前询问的只出现的一次的值 $q_i$，因为我们可以直接通过 $a_x,a_y$ 来计算得出 $a_i$ 的值，这是平凡的，在此不多赘述。

分析一下询问次数，发现支配区间每缩小一次都通过 $3$ 次询问问出了 $2$ 个数字，而其余情况下询问 $1$ 个数字只需要花费 $1$ 次询问。

由于最劣情况下支配区间可以缩小 $\displaystyle\frac{n}{2}$ 次，因此精细实现一下询问次数可以在 $1.5n$ 次询问内。

算法三：

$n + 5\log_4 n + 10$ 次询问。

考虑优化 $1.5n$ 次询问的做法，发现这个做法询问次数有点爆归根结底的原因是我们不知道更严格的支配区间 $[a_k,a_l]$ 的 $a_k,a_l$ 的相对大小关系。

我们不妨先考虑点简单的情况，考虑此时我们已经知道了两个数 $a_x,a_y$ 满足 $a_x < a_y$， 仍然考虑依次对没有获得任何信息的 $i$ 询问 $q_i = f(x,y,i)$，若此时对 $i$ 询问得出的所有值中存在三个数 $i,j,k$ 满足 $q_i = q_j = q_k$，则我们可以直接通过 $5$ 次询问得到 $a_i,a_j,a_k$ 的值，具体的，先询问 $f(x,i,j),f(x,i,k),f(x,j,k)$，此时我们可以得出 $a_i,a_j,a_k$ 中最大的数字（此例子我们设最大值为 $a_k$），则我们只需要再询问两次 $f(x,i,y),f(x,j,y)$ 即可。

此时我们知道了五个数 $a_x,a_i,a_j,a_k,a_y$，设这五个数的大小关系为 $a_x < a_i < a_j < a_k < a_y$，此时五个数两两之间都可以形成一个新的支配区间，设 $len = a_y - a_x$，则此时必定有一个支配区间的长度 $\le \displaystyle \lfloor \frac{len}{4} \rfloor$，选择长度最短的一段区间来将原区间形成更小的一段支配区间，显然区间缩小的次数是 $\log_4 n$ 量级的，对于每次压缩区间，我们都多花费了 $5$ 次询问内问出了 $4$ 个数字（每个数字都有基础的一次询问），那么这样次数就只需要多花费 $5\log_4 n$ 次。

但是前面我们考虑的是简单的情况，我们该如何求出 $a_x,a_y$ 这两个数字呢？

考虑选取五个下标 $i,j,k,l,x$，每三个数进行一次询问（对 $a_i < a_j < a_k < a_l < a_x$ 的情况举例），此时会出现 $3$ 个 $a_i + a_x$，$2$ 个 $a_i + a_l$，$2$ 个 $a_j + a_x$，$1$ 个 $a_i + a_k$，$1$ 个 $a_j + a_l$，$1$ 个 $a_k + a_x$。

稍加思考即可发现，我们一定可以确定 $i,x$ 这两个下标上的值 $a_i,a_x$，其次我们可以依次确定 $j,k,l$ 的值，于是，我们成功在 $10$ 次询问内询问出了 $5$ 个数字，原问题在 $n + 5\log_4 n + 10$ 次询问内得以解决。

算法四：

$n + \log n + 10$ 次询问。

考虑先花费 $10$ 次询问问出前五个数字，选出数值最接近的两个数 $a_x,a_y(a_x < a_y)$，询问 $f(x,y,i)$，此时会有两种情况：

• $f(x,y,i) \neq a_y - a_x$，那么此时显然容易分讨求出 $a_i$ 的值。
• $f(x,y,i) = a_y - a_x$，说明此时有 $\min(a_x,a_y) < a_i < \max(a_x,a_y)$，只需要根据 $a_x,a_y$ 是否为权值 $\min,\max$ 询问 $f(y,\max,i)$ 或 $f(x,\min,i)$ 即可求出 $a_i$ 的值，求出 $a_i$ 的值后选取 $a_x \sim a_i$，$a_i \sim a_y$ 更小的一测将数值往里缩即可。

算法五：

先 shuffle 编号，假设排列是随机生成的。

考虑可以在还剩下某些数值的时候维护值域维护剩余数的可能值域集合来凹一点次数。

考虑先求出前 $n - 1200$ 个数字，并取最接近 $\displaystyle\frac{n}{2}$ 的数 $a_p$。

对于剩下 $1200$ 个数维护其可能的数值集合，每次取未确定的三个 $a_x,a_y,a_z$，询问 $f(p,x,y),f(p,x,z)$，维护 $a_x,a_y,a_z$ 所有可能的数值三元组 $(p,q,r)$，若某一维所有可能的数字都相同则可以直接确定其值。

否则，若还有未确定的 $a_x,a_y,a_z$，设某一维数值为 $u$ 的个数为 $c_u$ 个，且这一维的出现数值集合为 $V$，目前所有可能的数值三元组个数为 $m$，则你求出一个值后期望剩余情况为 $\displaystyle \sum_{i \in V}^{} \frac{c_i}{m} \times c_i$，这样数值越小则说明其值域分布越均匀，每次花费一次询问直接询问出其数值最小的数即可。

实测可做到 $\le 99970$ 次询问，应该可以更优。