19014번 - Fair Competition 다국어인터랙티브

문제

This is an interactive problem.

There are competitions where you can take the top line of the standings and get a diploma for place zero, and the team below gets the cup for the first place.

Let us generalize this case. Suppose that $n$ guys participated in the competition, there are no ties, and the participants' places are consecutive integers. There are first, second, and third places, but the top line of the standings can correspond to a place smaller than the first. Suppose that such a competition was completed and you were asked to find out each person's final place. You can ask the participants about what place they took compared to other participants. However, participants will not always answer your questions. It depends who and whom you ask about, namely:

• Each participant who took a place higher than the first place answers only about those who are below him;
• The participant who took the first place will not say anything about anyone;
• The participant who took the second place can only answer that he performed better than the third place, and will not answer anything about others;
• The participant who took the third place answers only about those below him;
• Each participant who ranked below the third place answers only about those who are above him.

Determine the places of all participants.

입력

출력

제한

프로토콜

At the beginning, the jury program prints one line containing one integer $n$ (3ドル \leq n \leq 1000$). It is guaranteed that there are first, second, and third places, but the top line of the standings can correspond to a place smaller than the first. To ask questions, the parcitipants are numbered from 1ドル$ to $n$ in some order which is not relevant to their places.

After that, the participant program must interact with the jury program by printing the commands in one of the following formats:

• "? $a$ $b$". You ask the participant number $a$ how his place compares with the place of another participant number $b$. As a response, the jury program will output "+"' if the participant number $a$ said that he performed better than the participant number $b,ドル "-" if he said that he performed worse, and "?" if he decided not to answer.
• "! $\mathit{ans}$". The answer to the problem. Here, $\mathit{ans}$ is a sequence of integers denoting the places taken by participants with numbers from 1ドル$ to $n$. After printing this command, the program should terminate immediately.

Your solution can make at most 14,000 queries.

힌트

In each test for this problem, the places of all participants are fixed in advance and do not depend on your queries in any way.