CF1267I.Intriguing Selection

这是一个交互式问题。

你是一家国际象棋俱乐部的主教练。俱乐部有 $2n$ 名选手，每位选手都有一个用数字表示的实力值，且所有这些数字都互不相同。你并不知道这些选手的实力值。

你需要从中选出 $n$ 名选手，代表你的俱乐部参加即将到来的锦标赛。很自然地，你希望选出实力最强的 $n$ 名选手。

为此，你可以安排选手之间进行对局。在每一场对局中，你选择两名选手，他们进行比赛，你可以得知这两人中谁的实力更强。在决定下一场对局的参赛选手之前，你可以等待上一场比赛的结果。

然而，你并不希望完全了解这 $n$ 名选手之间的强弱关系，因为那样会让锦标赛本身变得不那么有趣。更正式地说，你必须让比赛结果达到这样一种状态：只有一种方式可以选出实力最强的 $n$ 名选手，并且根据你组织的比赛结果，关于这 $n$ 名选手的实力顺序，至少存在两种可能的排列。

你的程序需要在一次运行中处理多个测试用例。首先，读取整数 $t$（$t \ge 1$）——表示测试用例的数量。然后，依次处理每个测试用例。

在每个测试用例中，你的程序首先读取整数 $n$（$3 \le n \le 100$）——表示需要从 $2n$ 名选手中选出 $n$ 名选手。所有测试用例中 $n$ 的平方和不超过 $10\,000$。

接下来，你可以安排零场或多场对局。每安排一场对局，你需要输出一行格式为 ? $i$ $j$ 的描述——问号后跟两名参赛选手的编号。选手编号从 1 到 $2n$。输出对局描述后，记得刷新输出流。然后，你需要读取比赛结果——如果第一名选手实力更强，结果为大于号（>）；如果第二名选手实力更强，结果为小于号（<）。

你最多可以安排 $4n^2$ 场对局。安排完所有对局后，你需要输出一行感叹号（!），然后继续下一个测试用例。如果这是最后一个测试用例，则正常退出。输出感叹号后记得刷新输出流。

你组织的比赛结果必须保证：只有一种方式可以选出实力最强的 $n$ 名选手，并且关于这 $n$ 名选手的实力顺序，至少存在两种可能的排列。

评测程序会在你的程序开始安排比赛前，为所有选手分配互不相同的实力值，并据此回答你的比赛请求。

你的程序需要在一次运行中处理多个测试用例。首先，读取整数 $t$（$t \ge 1$）——表示测试用例的数量。然后，依次处理每个测试用例。

在每个测试用例中，你的程序首先读取整数 $n$（$3 \le n \le 100$）——表示需要从 $2n$ 名选手中选出 $n$ 名选手。所有测试用例中 $n$ 的平方和不超过 $10\,000$。

接下来，你可以安排零场或多场对局。每安排一场对局，你需要输出一行格式为 ? $i$ $j$ 的描述——问号后跟两名参赛选手的编号。选手编号从 1 到 $2n$。输出对局描述后，记得刷新输出流。然后，你需要读取比赛结果——如果第一名选手实力更强，结果为大于号（>）；如果第二名选手实力更强，结果为小于号（<）。

你最多可以安排 $4n^2$ 场对局。安排完所有对局后，你需要输出一行感叹号（!），然后继续下一个测试用例。如果这是最后一个测试用例，则正常退出。输出感叹号后记得刷新输出流。

你组织的比赛结果必须保证：只有一种方式可以选出实力最强的 $n$ 名选手，并且关于这 $n$ 名选手的实力顺序，至少存在两种可能的排列。

评测程序会在你的程序开始安排比赛前，为所有选手分配互不相同的实力值，并据此回答你的比赛请求。

在示例中，第一个测试用例中的选手按实力从高到低排序。根据示例输出中的比赛结果，我们可以推断出选手 1、2 和 3 是实力最强的三人，但我们无法确定选手 1 和选手 2 之间的强弱关系。

由 ChatGPT 4.1 翻译