26273번 - 모모의 아지트에 잠입하자! 인터랙티브

이 문제는 Interactive 문제입니다.

샤미코는 모모의 아지트에 잠입하려고 합니다. 하지만, 모모의 아지트 문은 비밀번호로 굳게 잠겨있습니다. 비밀번호는 $1$부터 $N$까지의 정수로 이루어진 길이 $N$의 순열 $\sigma$입니다.

샤미코는 모모의 아지트에 잠입하기 위해 비밀번호를 알아내려고 합니다. 샤미코는 여러 비밀번호를 시도해보다가 잠금장치에서 나는 소리를 잘 들으면 비밀번호에 대한 정보를 알 수 있다는 점을 발견했습니다. 구체적으로는, $1$부터 $N$까지의 정수로 이루어진 길이 $N$의 순열 $\pi$를 정해서 잠금장치에 입력하면 ($\sigma$와 $\pi$의 길이가 가장 긴 공통된 부분수열의 길이) 번만큼 톱니바퀴가 돌아가는 소리가 난다는 점입니다.

샤미코는 모모가 아지트로 돌아오기 전에 잠입을 하려 합니다. 시간에 늦지 않기 위해서는 $1\,000$번 이하의 시도로 문의 잠금장치를 해제해야 합니다. 샤미코와 함께 모모의 아지트 비밀번호 $\sigma$를 알아내봅시다.

당신은 처음에 순열의 길이 $N$을 표준 입력으로부터 입력받아야 합니다.

그 이후, 당신은 매 질의를 표준 출력으로 하나의 줄에 "? $\pi_1$ $\pi_2$ $\cdots$ $\pi_N$"과 같은 형태로 출력한후 표준 출력 버퍼를 flush 해야합니다. 이는 순열 $\pi = (\pi_1, \pi_2, \cdots, \pi_N)$를 잠금장치에 입력한다는 의미입니다. 언어별로 표준 출력 버퍼를 flush하는 방법은 다음과 같습니다. 기타 언어는 각 언어의 레퍼런스 페이지를 참고하시기 바랍니다.

• C: fflush(stdout);
• C++: std::cout << std::flush;
• Java: System.out.flush();
• Python: sys.stdout.flush()

질의 이후에, 표준 입력으로 하나의 줄에 한 개의 정수가 주어집니다. 이는 다음을 의미합니다.

• $-1$: 질의가 잘못되었거나, $1\,000$번이 넘는 질의를 했습니다. 추가적인 Interaction은 존재하지 않고, 프로그램을 즉시 종료해야 합니다.
• $1$ 이상 $N$ 미만의 정수 $L$: $\sigma$와 $\pi$의 길이가 가장 긴 공통된 부분수열의 길이가 $L$임을 의미합니다.
• $N$: $\sigma = \pi$인 경우로, 해당 테스트 케이스에 대한 정답을 맞춘 경우입니다. 추가적인 Interaction은 존재하지 않고, 프로그램을 즉시 종료해야 합니다.

$\sigma$는 첫 질의 전에 정해져 있으며, 바뀌지 않습니다.

• $N \le 100$
• 쿼리는 최대 $1\,000$번 사용할 수 있습니다.
• 이 문제의 테스트 케이스 개수는 $100$개를 넘지 않습니다.

$B$가 $A$의 부분수열이라는 것은, $1 \le i_1 < i_2 < \cdots < i_{\lvert B \rvert} \le \lvert A \rvert$가 존재해서 $1 \le j \le \lvert B \rvert$에 대해 $A_{i_j} = B_j$라는 것을 의미합니다.