Finding Array Tutorial

이 문제는 인터랙티브 문제다.

$1$ 이상 $1\\,000$ 이하의 $N$개의 정수로 이루어진 배열 $A = \[A\_{1}, A\_{2}, \cdots, A\_{N}]$가 있다. 배열의 원소 중 자신과 같은 값을 가진 원소가 다른 위치에 존재하지 않는 경우 이를 고유한 원소라고 한다.

당신은 이 배열의 원소들을 알지 못하는 상태이다. 당신은 다음과 같은 질문을 최대 $2N$번 할 수 있다.

• $?$ $L$ $R$: 배열 $A$의 부분 배열 $\[A\_{L}, A\_{L+1}, \cdots, A\_{R-1}, A\_{R}]$의 원소 중 고유한 원소의 개수를 질문한다.

이 질문을 이용해 배열 $A$에서 모든 고유한 원소의 위치를 찾아내야 한다.

첫째 줄에 배열의 길이 $N$ 이 주어진다. $(2 \leq N \leq 1\\,000)$

여러분은 다음 두 가지 유형의 상호작용을 표준 출력을 통해 할 수 있다. 각 질문은 한 개의 줄로 이루어져 있으며, 각 줄의 마지막에 개행 문자를 출력한 뒤 표준 출력 버퍼를 비워야 한다.

• $?$ $L$ $R$: 배열 $A$의 부분 배열 $\[A\_{L}, A\_{L+1}, \cdots, A\_{R-1}, A\_{R}]$의 원소 중 고유한 원소의 개수를 질문한다.

  • 질문은 아래 제약 사항을 모두 만족해야 한다.

    • $L$과 $R$은 다음 조건을 만족한다. : $1 \leq L \leq R \leq N$
    • 이 질문은 최대 $2N$번 할 수 있다.

  • 이 질문 이후에, 표준 입력으로 하나의 줄에 한 개의 정수가 주어진다. 이는 배열 $A$의 부분 배열 $\[A\_{L}, A\_{L+1}, \cdots, A\_{R-1}, A\_{R}]$의 원소 중 고유한 원소의 개수이다.

• ! $K$ $i\_{1}$ $i\_{2}$ $\cdots$ $i\_{K}$: 배열의 고유한 원소를 모두 알아낸 경우 답변한다.

  • 답변은 아래 제약 사항을 모두 만족해야 한다.

    • $K$는 고유한 원소의 개수를 의미하며, 배열 $A$에서 $A\_{i\_{k}}$ $(1 \leq k \leq K)$들은 모두 고유한 원소여야 한다.
    • $i\_1, i\_2, \cdots, i\_K$는 오름차순으로 정렬되어 있어야 한다.

  • 일치한다면 맞았습니다!! 판정을 받고 불일치한다면 틀렸습니다 판정을 받는다. 추가적인 상호작용은 존재하지 않으며, 프로그램을 즉시 종료해야 한다.

다음과 같은 경우에는 예상하지 못한 채점 결과를 받을 수 있음에 유의한다.

• 매번 질문을 한 뒤 표준 출력 버퍼를 비우지 않았다.
• 출력 형식을 어겼다.
• $2N$번보다 많은 질문을 했다.
• 정답을 답변한 이후 프로그램을 즉시 종료하지 않았다.

배열 $A$는 첫 질문 전에 정해져 있으며, 바뀌지 않는다.

언어별로 표준 출력 버퍼를 비우는 방법은 다음과 같다. 이외의 언어는 각 언어의 레퍼런스 페이지를 참고하여라.

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