이것은 인터랙티브 문제입니다.

길이 $n=30000$인 순열 $p$가 심사자(Judge)에 의해 숨겨져 있습니다. 여러분의 작업은 이 순열의 최솟값이 있는 인덱스를 찾는 것입니다.

심사자는 비적응적(non-adaptive)입니다. 순열은 인터랙션이 시작되기 전에 정해지며 절대 변하지 않습니다.

일반적인 비교 쿼리와 달리, 심사자는 현재 쿼리를 이전 쿼리와만 비교합니다. 더 정확히 말하면, 이전에 쿼리한 인덱스가 $i$였고 이제 인덱스 $j$를 쿼리하면, 심사자는 $p_i$와 $p_j$의 비교 결과를 알려줍니다.

최대 $q_{\max}=42000$번의 쿼리를 할 수 있습니다.

공식 심사 데이터는 100개의 분리된 테스트 파일로 구성됩니다. 프로그램은 각 파일에 대해 독립적으로 실행됩니다.

인터랙션

인터랙션 시작 시, 프로그램은 두 개의 정수를 읽어야 합니다.

$$ n \quad q_{\max}. $$

공식 테스트에서 $n=30000$, $q_{\max}=42000$입니다.

쿼리를 하려면 다음 형식으로 한 줄을 출력하십시오.

$$ \text{? j} $$

여기서 $1 \le j \le n$입니다.

심사자는 한 문자로 응답합니다.

• < : $p_i < p_j$인 경우 (단, $i$는 이전 쿼리 인덱스를 의미하며, 해당되는 경우에만)
• = : 첫 번째 쿼리이거나 $p_i = p_j$인 경우
• > : $p_i > p_j$인 경우 (단, $i$는 이전 쿼리 인덱스를 의미하며, 해당되는 경우에만)

$p$는 순열이므로 첫 번째 쿼리 이후의 = 응답은 이전 쿼리와 동일한 인덱스를 쿼리한 경우에만 발생할 수 있습니다. 심사자가 -1로 응답하면 프로그램은 즉시 종료되어야 합니다. 이는 프로그램이 인터랙션 프로토콜을 위반했으며 Wrong Answer를 받게 됨을 의미합니다.

최종 답변을 제출하려면 다음 형식으로 한 줄을 출력하십시오.

$$ \text{! a} $$

여기서 $a$는 최솟값이 있다고 주장하는 인덱스입니다. 답변을 출력한 후 프로그램은 종료되어야 합니다. 최종 답변은 쿼리 횟수에 포함되지 않습니다.

프로그램이 $q_{\max}$회를 초과하여 쿼리하거나, 유효하지 않은 인덱스를 쿼리하거나, 유효하지 않은 명령을 출력하거나, 최종 답변이 틀리면 Wrong Answer를 받습니다.

쿼리 또는 답변을 출력한 후에는 출력 버퍼를 플러시(flush)해야 합니다. 예를 들어, C++에서는 endl 또는 cout.flush()를 사용할 수 있습니다.

참고

이 예제는 인터랙션 예시일 뿐이며 실제 테스트 데이터에는 포함되지 않습니다. (receiving ... output) 형식의 줄은 예제에서 쿼리와 심사자 응답을 정렬하기 위해 사용된 자리표시자입니다. 실제 테스트 케이스에서는 심사자가 이러한 자리표시자 줄을 출력하지 않으며, 참가자는 이를 읽거나 출력해서는 안 됩니다.

이 예제 인터랙션에서 숨겨진 순열은 $p=(3,1,4,2)$입니다. 아래 불릿 포인트는 예제에 나타난 인터랙션을 설명합니다.

• 심사자는 먼저 $n=4$와 쿼리 제한 $5$를 보냅니다.
• 첫 번째 쿼리 ? 1은 이전 쿼리 인덱스가 없으므로 =를 받습니다.
• 쿼리 ? 2는 $p_1=3$과 $p_2=1$을 비교하므로 심사자는 >로 응답합니다.
• 쿼리 ? 4는 $p_2=1$과 $p_4=2$를 비교하므로 심사자는 <로 응답합니다. 최솟값은 인덱스 $2$에 있으므로 ! 2가 정답입니다.

로컬 인터랙션 도구: 첨부된 attachments/local_interactive.py는 --perm 3,1,4,2 --limit 5를 사용하여 이 로컬 환경을 재현할 수 있지만, 이를 통과한다고 해서 공식 심사 데이터를 통과하는 것은 보장되지 않습니다.