순열 복원

$Q$는 $1$부터 $N$까지의 정수를 정확히 한 번씩 포함하는 순열이어야 한다. 같은 순열로 여러 번 질의해도 된다. 질의를 출력한 뒤에는 반드시 출력 버퍼를 flush해야 한다.

각 올바른 질의 뒤에는 정수 $L$을 입력받는다. $L$은 $R_i=P_{Q_i}$로 정의되는 순열 $R$의 사이클 중 가장 긴 사이클의 길이이다.

순열 $P$를 알아냈다면 다음 형식으로 최종 답을 출력한다.

$!\ P_1\ P_2\ \cdots\ P_N$

최종 답의 ! 출력은 $1600$번의 질의 제한에 포함되지 않는다. 최종 답이 숨겨진 순열 $P$와 다르면 오답이다. 최종 답을 출력한 뒤에도 출력 버퍼를 flush하고 프로그램을 즉시 종료해야 한다.

올바르지 않은 질의를 하거나 ? 형식의 질의를 $1600$번보다 많이 하면 -1을 입력받을 수 있다. 이 경우 프로그램을 즉시 종료해야 한다.

상호작용 예시

$N=3$, 숨겨진 순열이 $P=(2,3,1)$인 경우를 생각하자. 실제 상호작용에서는 $P$가 주어지지 않는다.

• 인터랙터가 3을 보낸다.
• 참가자가 ? 1 2 3을 출력하고 flush한다. 이때 $R=(2,3,1)$이므로 인터랙터는 3을 보낸다.
• 참가자가 ? 3 1 2를 출력하고 flush한다. 이때 $R=(1,2,3)$이므로 인터랙터는 1을 보낸다.
• 참가자가 ! 2 3 1을 출력하고 flush한 뒤 종료한다.

이 예시는 통신 형식과 응답의 의미를 설명하며, 순열을 알아내는 일반적인 방법을 제시하지 않는다.