이 문제는 인터랙티브 문제이다.
길이 의 숨겨진 순열 이 있다.
를 연속한 부분수열 의 가장 긴 증가하는 부분수열의 길이라고 정의한다. 증가하는 부분수열에서 원소의 값은 엄격하게 증가해야 한다.
당신은 인터랙터에게 구간을 질의하여 해당 구간의 를 알 수 있다. 최대 번의 질의를 사용하여 모든 에 대한 를 구하여라.
부분수열이란
주어진 수열에서 일부 항을 지우거나 남겨서, 원래의 순서를 유지한 채 만든 새로운 수열을 뜻한다.
처음에 참가자의 프로그램은 정수 을 입력받는다. 순열 는 참가자에게 주어지지 않는다.
구간 의 LIS 길이를 질의하려면 다음 형식으로 출력한다.
?
질의는 을 만족해야 한다. 인터랙터는 정수 를 출력한다.
모든 값을 알아냈다면 다음 형식으로 최종 답을 출력한다.
!
각 은 와 같아야 한다. 즉, 번째 줄에는 을 순서대로 출력한다.
각 질의와 최종 답을 출력한 뒤에는 반드시 출력 버퍼를 flush해야 한다.
질의 횟수는 최대 번이다. 올바르지 않은 질의를 출력하거나 질의 횟수를 초과하면 인터랙터는 을 출력하고 채점을 종료한다. 을 입력받은 경우 프로그램을 즉시 종료해야 한다.
최종 답을 출력한 뒤에는 더 이상 출력하지 않아야 한다.
