Это интерактивная задача.
Вы — главный тренер шахматного клуба. В клубе игроков, у каждого игрока есть некоторая сила, которую можно представить числом, и все эти числа различны. Силы игроков Вам не известны.
Вам следует выбрать игроков, которые будут представлять Ваш клуб в предстоящем чемпионате. Естественно, Вы хотите выбрать самых сильных игроков.
Для этого Вы можете организовывать матчи между игроками. В каждом матче Вы выбираете двух игроков, они играют несколько игр, и Вы узнаете, у кого из двоих больше сила. Вы можете дождаться исхода матча, прежде чем решить, кто будет участвовать в следующем.
Однако Вам нет необходимости знать, как эти игроков соотносятся по силе между собой, поскольку это сделало бы сам чемпионат менее интригующим. Более формально, Вы должны достичь состояния, в котором существует ровно один способ выбрать игроков с наивысшей силой, который соответствует результатам организованных Вами матчей. Однако должны быть как минимум два возможных порядка этих игроков по силе, соответствующие результатам организованных Вами матчей.
Ваша программа должна обработать несколько тестов. Сначала следует прочитать целое число — количество тестов. Затем следует обработать тесты один за другим.
В каждом тесте Ваша программа должна начинаться с чтения целого числа — количества игроков, которых нужно выбрать из игроков. Сумма квадратов значений по всем тестам не превышает .
Затем Ваша программа может организовывать матчи — ноль или более раз. Чтобы организовать матч, программа должна вывести описание матча в формате ? i j — вопросительный знак, за которым следуют два разных номера игроков, участвующих в матче. Игроки нумеруются от до включительно. Не забудьте очистить вывод после вывода описания матча. Затем программа должна прочитать результат матча — это будет либо символ "больше" (>), если первый игрок имеет более высокую силу, либо символ "меньше" (<), если у второго игрока сила выше.
Ваша программа может организовать не более матчей. После завершения матчей программа должна вывести восклицательный знак (!) и перейти к следующему тесту или корректно завершить работу, если это был последний тест. Не забудьте очистить вывод после печати восклицательного знака.
Должен быть ровно один способ выбрать игроков с наибольшей силой, соответствующий результатам организованных Вами матчей. Однако должно быть как минимум два возможных порядка этих игроков по их силе, которые соответствуют результатам организованных матчей.
Судейская программа выбирает несколько разных чисел в качестве сил всех игроков, прежде чем Ваша программа начнет организовывать матчи, и использовать их для ответа на запросы.
В первом тесте игроки отсортированы по силе в порядке убывания. Из матчей в примере мы можем сделать вывод, что игроки и имеют наибольшую силу, но мы не знаем, насколько игрок сравним с игроком .