406842: GYM102569 G Nuts and Bolts

Steven has $$$n$$$ nuts and $$$n$$$ bolts. All nuts have different sizes from 1 to $$$n$$$, and all bolts have different sizes from 1 to $$$n$$$.

The operation Steven can perform is to try to compare one of the nuts with one of the bolts. As a result he will learn if the size of nut is greater, the size of bolt is greater or these nut and bolt match. He wants to find the matching nut for every bolt.

You must help Steven to do the plan, using no more than $$$5 n \log_{2}n$$$ operations.

This is an interactive problem. Your program should communicate with the jury's program, using standard input and output for that.

At the beginning your program receives the integer $$$n$$$ ($$$2 \le n \le 1000$$$) — the number of nuts and bolts.

After that you can make no more than $$$5 n \log_{2}n$$$ queries. To do a query, output the character "?", and then numbers $$$i$$$ and $$$j$$$ ($$$1 \le i \le n, 1 \le j \le n$$$) — the number of nut and the number of bolt that Steven will try to compare.

As a result, you receive one of the three characters:

• "<", if the size of the $$$i$$$-th nut is less than the size of the $$$j$$$-th bolt,
• "=", if the $$$i$$$-th nut and the $$$j$$$-th bolt match,
• ">", if the size of the $$$i$$$-th nut is greater than the size of the $$$j$$$-th bolt.

As soon as you can say which nut matches which bolt, output the character "!", and then $$$n$$$ distinct integers $$$p_i$$$ ($$$1 \le p_i \le n$$$), where $$$p_i$$$ is the number of bolt which matches the nut with the number $$$i$$$. After that your program must terminate.

5

<

<

>

>

<

=

=

=

=

=

? 1 1

? 2 2

? 3 3

? 4 4

? 5 5

? 1 4

? 2 3

? 3 2

? 4 5

? 5 1

! 4 3 2 5 1

Please note that each your message must end with a line break. Also after outputting each message your program must flush the stream buffer, so that the outputted information could reach jury's program: for instance, this can be done by calling "fflush(stdout)" or "cout.flush()" in C++, "System.out.flush()" in Java, "Console.Out.Flush()" in C#, "flush(output)" in Pascal, "sys.stdout.flush()" in Python.

Emply lines in the sample are given only for convenience, to make it clear in which order the messages are written. When solving the problem you must not output empty lines and jury's program won't output empty lines too.