Intriguing Selection

题意翻译

- 这是一道交互题。 - 有 $2n$ 个各不相同的数 $a[1\dots 2n]$。你可以询问至多 $4n^2$ 次 $(i,j)$ 并得知是 $a_i>a_j$ 还是 $a_i<a_j$。 - 通过这些询问，你需要确定最大的 $n$ 个数，但也要保证这整个序列并没有完全被确定 。完成后输出 ！表示结束。 - $3 \le n \le 100$，多组数据 $ \sum n^2 \le 10000$

题目描述

This is an interactive problem. You are the head coach of a chess club. The club has $ 2n $ players, each player has some strength which can be represented by a number, and all those numbers are distinct. The strengths of the players are not known to you. You need to select $ n $ players who would represent your club in the upcoming championship. Naturally, you want to select $ n $ players with the highest strengths. You can organize matches between the players to do that. In every match, you pick two players, they play some games, and you learn which one of the two has higher strength. You can wait for the outcome of a match before deciding who will participate in the next one. However, you do not want to know exactly how those $ n $ players compare between themselves, as that would make the championship itself less intriguing. More formally, you must reach a state where there is exactly one way to choose $ n $ players with the highest strengths that is consistent with the outcomes of the matches you organized, but there must be at least two possible orderings of those $ n $ players by strength that are consistent with the outcomes of the matches you organized.

输入输出格式

输入格式

输出格式

Your program has to process multiple test cases in one run. First, it should read the integer $ t $ ( $ t \ge 1 $ ) — the number of test cases. Then, it should process the test cases one by one. In each test case, your program should start by reading the integer $ n $ ( $ 3 \le n \le 100 $ ) — the number of players to select out of $ 2n $ players. The sum of squares of the values of $ n $ over all test cases does not exceed $ 10\,000 $ . Then your program can organize matches zero or more times. To organize a match, your program should print a match description formatted as ? $ i $ $ j $ — a question mark followed by two distinct numbers of players participating in the match. The players are numbered from 1 to $ 2n $ , inclusive. Remember to flush the output after printing the match description. Then your program should read the match outcome — it will be either the greater-than character (>), if the first player in the match description has higher strength, or the less-than character (<), if the second player in the match description has higher strength. Your program can organize at most $ 4n^2 $ matches. After it is done organizing matches, it should print the exclamation mark (!) and continue to the next test case, or exit gracefully if this was the last test case. Remember to flush the output after printing the exclamation mark. There must be exactly one way to choose $ n $ players with the highest strength that is consistent with the outcomes of the matches you organized, but there must be at least two possible orderings of those $ n $ players by their strength that are consistent with the outcomes of the matches you organized. The judging program picks some distinct numbers as the strengths of all players before your program starts organizing matches and uses them to answer the requests.

输入输出样例

输入样例 #1

2
3

>

<

>

<

>

>

3

<

<

<

>

>

输出样例 #1

? 1 3

? 4 2

? 4 5

? 6 5

? 3 4

? 5 6

!

? 3 4

? 4 2

? 5 3

? 6 4

? 3 1

!

说明

In the example, the players in the first test case are sorted by strength in decreasing order. From the matches in the example output, we can deduce that players 1, 2, and 3 have the highest strength, but we do not know how the player 1 compares to the player 2.