Это сложная версия задачи. В этой версии вы должны использовать минимально возможное количество запросов. Вы можете совершать взломы только в том случае, если решены обе версии задачи.

Это интерактивная задача.

На сборах сборной Мексики к IOI существует традиция играть в игру «Ассасин», которая похожа на «Among Us» или «Мафию».

Сегодня $$$n$$$ игроков, пронумерованных от $$$1$$$ до $$$n$$$, будут играть в «Ассасин» со следующими тремя ролями:

• Рыцарь: Рыцарь — это тот, кто всегда говорит правду.
• Лжец: Лжец — это тот, кто всегда лжет.
• Предатель: Предатель — это тот, кого все считают Рыцарем, а на самом деле он Лжец.

Каждому игроку будет назначена своя роль в игре. В игре будет ровно один Предатель, но может быть любое (возможно нулевое) количество Рыцарей и Лжецов.

Вы были ведущим игры, но случайно забыли роли всех игроков, поэтому вам нужно определить игрока, который является Предателем.

Чтобы определить Предателя, вы зададите несколько вопросов. В каждом вопросе вы выбираете двух игроков $$$i$$$ и $$$j$$$ ($$$1 \leq i, j \leq n$$$; $$$i \neq j$$$) и спрашиваете, считает ли игрок $$$i$$$, что игрок $$$j$$$ — Рыцарь. Результаты этого вопроса приведены в таблице ниже.

Найти Предателя за минимально возможное количество запросов. Иными словами, пусть $$$f(n)$$$ — минимальное число, такое, что для $$$n$$$ игроков существует стратегия, позволяющая определить Предателя, используя не более $$$f(n)$$$ вопросов. Тогда для определения Предателя нужно использовать не более $$$f(n)$$$ вопросов.

Заметьте, что итерактор адаптивен: роли игроков не фиксированы изначально и могут меняться в зависимости от ваших вопросов. Однако гарантируется, что существует такое распределение ролей, которое соответствует всем ранее заданным вопросам в ограничениях этой задачи.

Чтобы задать вопрос, выведите строку в следующем формате:

• «? i j» ($$$1 \leq i,j \leq n$$$; $$$i \neq j$$$) — спросить игрока $$$i$$$, считает ли он игрока $$$j$$$ Рыцарем.

Жюри выдаст «1», если игрок $$$i$$$ считает игрока $$$j$$$ Рыцарем, и «0» в противном случае.

Когда вы определите, какой игрок является Предателем, выведите строку в следующем формате:

• «! i» ($$$1 \leq i \leq n$$$) — Предателем является игрок $$$i$$$.

Обратите внимание, что ответы не учитываются в ограничении в $$$f(n)$$$ вопросов.

Если вы сделали некорректный вывод, использовали более $$$f(n)$$$ вопросов или неверно определили Предателя, жюри ответит «-1», и вы получите вердикт Неправильный ответ. Получив «-1», ваша программа должна немедленно завершиться. В противном случае вы можете получить произвольный вердикт, поскольку ваше решение продолжит чтение из закрытого потока.

После каждого вывода не забудьте вывести перевод строки и сбросить буфер вывода. В противном случае вы получите вердикт Решение «зависло». Для сброса буфера используйте:

• fflush(stdout) или cout.flush() в C++;
• System.out.flush() в Java;
• sys.stdout.flush() в Python;
• std::io::stdout().flush() в Rust;
• смотрите документацию для других языков.

Формат взломов

Для взломов используйте следующий формат.

Первая строка должна содержать одно целое число $$$t$$$ — количество наборов входных данных.

Первая строка каждого набора входных данных должна содержать целое число $$$n$$$, за которым следует строка «manual».

Вторая строка содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$-1 \le a_i \le 1$$$) — роли каждого игрока. $$$1$$$ обозначает Рыцаря, $$$0$$$ — Лжеца, а $$$-1$$$ — Предателя. Предатель должен быть ровно один, то есть должен быть ровно один индекс $$$i$$$ такой, что $$$a_i=-1$$$.

В качестве примера приводим взлом, аналогичный примеру из условия:

2
7 manual
0 1 0 -1 0 1 0
4 manual
0 1 -1 0