문제

Ivan wants to play a game with you. He took all integers from $1$ to $n$ inclusive, shuffled them and then put all even numbers into array $e$ and all odd numbers into array $o$.

Your task is to find arrays $e$ and $o$.

You can ask Ivan questions of certain kind. Each question consists of two integers $i$ and $j$. For each question Ivan says whether $e[i] < o[j]$ or not.

You can ask at most $300\, 000$ questions.

입력

출력

상호작용

First, the testing system writes the integer $n$ ($1 \le n \le 10\,000$) — the number of integers Ivan used.

Your solution shall print requests of two types:

• "? $i$ $j$". $1 \le i \le \lfloor \frac{n}{2} \rfloor, 1 \le j \le \lceil \frac{n}{2} \rceil$. The testing system responds with the symbol "<" if $e[i] < o[j]$ or with the symbol ">" otherwise.
• "! $e_1~e_2~...~e_{\lfloor \frac{n}{2} \rfloor}~o_1~o_2~...~o_{\lceil \frac{n}{2} \rceil}$" tells the values of $e$ and $o$ that your program has determined.

Don't forget to flush the output after each request!

Your solution must issue exactly one request of the second type, which must be the last request, and the solution must terminate gracefully after issuing it.

Your solution is allowed to issue at most $300\,000$ requests of the first type.

For each test case the number $n$ is fixed and the numbers are shuffled using Java built-in shuffle function with fixed seed.

예제 입력 1

5
>
>
<
>
<
<

예제 출력 1

? 1 1
? 1 2
? 1 3
? 2 1
? 2 2
? 2 3
! 4 2 1 3 5