Este es un problema interactivo.

El juez oculta una permutación $p$ de longitud $n=30000$. Tu tarea es encontrar el índice del valor mínimo de esta permutación.

El juez no es adaptativo: la permutación se elige antes de que comience la interacción y nunca cambia.

A diferencia de las consultas de comparación ordinarias, el juez solo compara tu consulta actual con tu consulta anterior. Más precisamente, si tu índice consultado anteriormente fue $i$ y ahora consultas el índice $j$, el juez te indica la comparación entre $p_i$ y $p_j$.

Puedes realizar como máximo $q_{\max}=42000$ consultas.

Los datos de evaluación oficiales constan de 100 archivos de prueba separados. Tu programa se ejecuta de forma independiente en cada archivo.

Interacción

Al comienzo de la interacción, tu programa debe leer dos enteros

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

Para las pruebas oficiales, $n=30000$ y $q_{\max}=42000$.

Para realizar una consulta, imprime una línea con el siguiente formato:

$$ \text{? j} $$

donde $1 \le j \le n$.

El juez responde con un carácter:

• `<$ si $p_i < p_j$, donde $i$ denota la consulta anterior (si corresponde);
• `=$ si esta es la primera consulta, o si $p_i = p_j$;
• `>$ si $p_i > p_j$, donde $i$ denota la consulta anterior (si corresponde).

Como $p$ es una permutación, la respuesta =$ después de la primera consulta solo puede ocurrir si consultas el mismo índice que en la consulta anterior. Si el juez responde con-1`, tu programa debe terminar inmediatamente. Esto significa que tu programa ha violado el protocolo de interacción y recibirá Wrong Answer.

Para dar tu respuesta final, imprime una línea con el siguiente formato:

$$ \text{! a} $$

donde $a$ es el índice que afirmas que contiene el valor mínimo. Después de imprimir la respuesta, tu programa debe terminar. La respuesta final no cuenta como consulta.

Si tu programa realiza más de $q_{\max}$ consultas, consulta un índice inválido, imprime un comando inválido o da una respuesta final incorrecta, recibe Wrong Answer.

Después de cada consulta o respuesta impresa, vacía el búfer de salida. Por ejemplo, en C++ puedes usar endl o cout.flush().

Nota

Este ejemplo es solo una interacción de muestra y no aparecerá en los datos de prueba reales. Las líneas de la forma (recibiendo ... salida) son marcadores de posición utilizados únicamente para alinear las consultas y las respuestas del juez en el ejemplo. En un caso de prueba real, el jurado no generará estas líneas de marcador de posición, y el participante no debe leerlas ni imprimirlas.

En este ejemplo de interacción, la permutación oculta es $p=(3,1,4,2)$. Los puntos siguientes describen la interacción que se muestra en el ejemplo.

• El juez primero envía $n=4$ y el límite de consultas $5$.
• La primera consulta ? 1 recibe `=$ porque no hay ningún índice consultado anteriormente.
• La consulta ? 2 compara $p_1=3$ con $p_2=1$, por lo que el juez responde `>$ .
• La consulta ? 4 compara $p_2=1$ con $p_4=2$, por lo que el juez responde <$ . El mínimo está en el índice $2$, por lo que! 2` es correcto.

Herramienta de interacción local: El archivo adjunto attachments/local_interactive.py puede reproducir esta configuración local con --perm 3,1,4,2 --limit 5, pero pasarlo no garantiza pasar los datos de evaluación oficiales.