CF730B Minimum and Maximum

这是一个交互式问题。你需要在输出每一行后立即刷新输出。例如，在 C++ 中你应该使用函数 fflush(stdout)，在 Java 中使用 System.out.flush()，在 Pascal 中使用 flush(output)，在 Python 中使用 sys.stdout.flush()。 在本题中，你需要找出一个数组中的最大值和最小值。还有比这更简单的事吗？ 你可以想象裁判有一个数组，而你最开始只知道一个数字 $n$，即数组的长度。 数组元素编号为 $1$ 到 $n$。你被允许通过指定下标 $i$ 和 $j$ 来比较数组中的两个元素。对于每次比较，可能返回三种结果：「」（如果 $a_{i} > a_{j}$）。 已知总是可以通过不超过 $f(n)=\lceil \frac{3n}{2} \rceil -2$ 次比较找出数组的最小值和最大值，这里 $\lceil x \rceil$ 表示向上取整。 请你写一个程序，通过不超过 $f(n)$ 次比较，找出长度为 $n$ 的数组的最小值和最大值的下标。

本题的每个测试包含一个或多个数组。你需要为每个数组找出最大和最小元素的位置。输入的第一行包含整数 $T$（$1 \leq T \leq 1000$），表示测试数组的数量。 因此，程序首先应读取数字 $T$，然后依次为 $T$ 个数组解决问题。 接下来是每个数组的输入。首先，你需要读取一个整数 $n$（$1 \leq n \leq 50$），表示当前数组的长度。 随后，你可以选择进行比较或报告答案。 - 若要进行一次比较，应输出形如「? i j」的字符串（$i$ 和 $j$ 均为 $1$ 到 $n$ 之间的整数），表示询问当前数组第 $i$ 个和第 $j$ 个元素的关系； - 若要报告最小值和最大值的位置，应输出「! i j」这样的字符串，其中 $i$ 是最小元素在数组中的下标，$j$ 是最大元素的下标。如果有多个答案，输出任意一个即可。 比较的结果可能是： - '' — 如果 $a_{i} > a_{j}$。 对于长度为 $n$ 的数组，你最多只能进行 $f(n)$ 次比较。注意，报告答案操作「! i j」不计入 $f(n)$ 次数。 在报告完一个数组的答案后，程序需开始处理下一个数组，或者全部 $T$ 个数组处理完毕后结束。

无。

无。 由 ChatGPT 5 翻译