This is the hard version of the problem. In this version, you must use the minimum number of queries possible. You can make hacks only if both versions of the problem are solved.

This is an interactive problem.

It is a tradition in Mexico's national IOI trainings to play the game "Asesino", which is similar to "Among Us" or "Mafia".

Today, $$$n$$$ players, numbered from $$$1$$$ to $$$n$$$, will play "Asesino" with the following three roles:

• Knight: a Knight is someone who always tells the truth.
• Knave: a Knave is someone who always lies.
• Impostor: an Impostor is someone everybody thinks is a Knight, but is secretly a Knave.

Each player will be assigned a role in the game. There will be exactly one Impostor but there can be any (possible zero) number of Knights and Knaves.

As the game moderator, you have accidentally forgotten the roles of everyone, but you need to determine the player who is the Impostor.

To determine the Impostor, you will ask some questions. In each question, you will pick two players $$$i$$$ and $$$j$$$ ($$$1 \leq i, j \leq n$$$; $$$i \neq j$$$) and ask if player $$$i$$$ thinks that player $$$j$$$ is a Knight. The results of the question is shown in the table below.

Find the Impostor in the minimum number of queries possible. That is, let $$$f(n)$$$ be the minimum integer such that for $$$n$$$ players, there exists a strategy that can determine the Impostor using at most $$$f(n)$$$ questions. Then, you should use at most $$$f(n)$$$ questions to determine the Impostor.

Note: the grader is adaptive: the roles of the players are not fixed in the beginning and may change depending on your questions. However, it is guaranteed that there exists an assignment of roles that is consistent with all previously asked questions under the constraints of this problem.

To ask a question, output a line in the following format:

• "? i j" ($$$1 \leq i,j \leq n$$$; $$$i \neq j$$$) — to ask player $$$i$$$ if they think player $$$j$$$ is a Knight.

The jury will output a "1" if player $$$i$$$ thinks player $$$j$$$ is a Knight, and "0" otherwise.

When you have determined which player the Impostor is, output a line in the following format:

• "! i" ($$$1 \leq i \leq n$$$) — the Impostor is player $$$i$$$.

Note that answering does not count to your limit of $$$f(n)$$$ questions.

If you have made an invalid output, used more than $$$f(n)$$$ questions or wrongly determined the Impostor, the jury will respond with "-1" and you will receive a Wrong Answer verdict. Upon receiving "-1", your program must terminate immediately. Otherwise, you may receive an arbitrary verdict because your solution might be reading from a closed stream.

After printing a query do not forget to output the end of the line and flush the output. Otherwise, you will get Idleness limit exceeded. To do this, use:

• fflush(stdout) or cout.flush() in C++;
• System.out.flush() in Java;
• sys.stdout.flush() in Python;
• std::io::stdout().flush() in Rust;
• see the documentation for other languages.

Hack format

For hacks, use the following format.

The first line should contain a single integer $$$t$$$ — the number of test cases.

The first line of each test case should contain the integer $$$n$$$ followed by the string "manual".

The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$-1 \le a_i \le 1$$$) — the roles of each player. $$$1$$$ denotes a Knight, $$$0$$$ denotes a Knave, and $$$-1$$$ dentoes an Impostor. There must be exactly one Impostor, that is there must be exactly one index $$$i$$$ such that $$$a_i=-1$$$.

As an example, the hack format for the example input is:

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