Este es un problema interactivo.
En la permutación p=(1,2,\ldots,n) se intercambiaron dos elementos situados en las posiciones y (1\le i<j\le n).
En una consulta puedes elegir un segmento [l,r] y averiguar la cantidad de inversiones en p_l,p_{l+1},\ldots,p_r, es decir, la cantidad de pares de índices tales que l\le u<v\le r y p_u>p_v.
Encuentra y usando a lo sumo consultas por caso de prueba. La permutación oculta se fija antes de que comience la interacción y no cambia.
Primero, el interactor envía un número entero (1\le t\le100) — la cantidad de casos de prueba.
Antes de cada caso de prueba, el interactor envía un número entero (2\le n\le10^4) — la longitud de la permutación. Los valores y están ocultos.
Para hacer una consulta, imprime en una línea aparte ? l r, donde 1\le l\le r\le n. El interactor responde con un número entero — la cantidad de inversiones en ese segmento.
Cuando encuentres la respuesta, imprime en una línea aparte ! i j, donde 1\le i<j\le n. Imprimir la respuesta no cuenta como consulta.
Tras una respuesta correcta, el interactor envía de inmediato el valor del siguiente caso de prueba, si lo hay. No se envía ninguna confirmación adicional. Después de responder el último caso de prueba, termina tu programa.
Después de cada comando, imprime un salto de línea y vacía el búfer de salida: por ejemplo, usa cout.flush() en C++ o flush=True en Python.
Un comando inválido, una respuesta incorrecta o exceder el límite de consultas producen el veredicto Wrong Answer. Cada comando debe contener exactamente dos parámetros enteros. Si recibes o alcanzas el final del flujo de entrada, termina tu programa de inmediato.
Ejemplo 1
Ejemplo 2
Ejemplo 3
En los ejemplos, la columna de entrada contiene los mensajes del interactor y la columna de salida contiene los comandos del programa en su orden de ejecución.
En el primer ejemplo, p=(1,4,3,2,5). El interactor envía primero t=1 y n=5. Responde tanto a ? 1 5 como a ? 2 4, tras lo cual el programa imprime ! 2 4.
En el segundo ejemplo, p=(2,1). En el tercer ejemplo, p=(4,2,3,1): todo el segmento tiene inversiones, mientras que el segmento tiene .
Subtarea ( puntos): n\le4.
Subtarea ( puntos): n\le15.
Subtarea ( puntos): i=1.
Subtarea ( puntos): sin restricciones adicionales.