Larry the magical panda is bored of eating bamboo cookies, so he challenges you to a game. He has a permutation of which he calls , and you have to guess the permutation by asking questions. The questions work as follows:
- You will give Larry two distinct indices and
- Larry will respond with the result of
Larry allows you to ask at most questions. Can you guess the permutation and win the game?
Subtask 1 [10%]
Subtask 2 [90%]
No additional constraints.
This is an interactive problem, where you and the judge exchange information back-and-forth to solve the problem.
At first, you should read in a line containing the integer .
You will then start the interaction by proceeding with your questions. Each question should be formatted as
? i j followed by a
\n character, with and . In response, you will be given on its own line.
If you believe you have the solution, you may output
! followed by a space-separated list of integers , the permutation . You must terminate your program immediately after performing this operation. Note that this operation does not count towards the limit of questions.
If at any point you attempt an invalid question (such as an invalid output format or a prohibited pair of indices), or you exceed the limit of questions, the interactor will respond with . You should terminate your program immediately after receiving this feedback to receive a Wrong Answer verdict, or you may receive an arbitrary verdict. If the final list you output is incorrect, you will receive a Wrong Answer verdict. Otherwise, you will receive a verdict of Accepted for the corresponding test case.
Please note that you may need to flush
stdout after each operation, or interaction may halt. In C++, this can be done with
cout << flush (depending on whether you use
cout). In Java, this can be done with
System.out.flush(). In Python, you can use
>>> denotes your output. Do not print this out.
5 >>> ? 4 5 5 >>> ? 2 4 3 >>> ? 2 3 6 >>> ! 4 3 2 1 5