Ganhar em 145

Este problema é interativo.

Luigi percorre uma fase com $n$ blocos em fila. Cada bloco $i$ esconde um valor $a_i$ , e os valores estão ordenados de forma estritamente crescente. Luigi pode golpear um bloco para descobrir seu valor, mas, como em toda fase do Luigi, ele só pode avançar para a direita.

As consultas têm duas restrições:

Cada consulta deve ser a uma posição estritamente maior que a da consulta anterior.
Luigi tem uma única vida extra: ele pode reiniciar a fase uma única vez. Ao reiniciar, a consulta seguinte pode ser a qualquer posição e, a partir daí, a restrição anterior volta a valer.

Dado um valor $x$ que aparece em algum bloco, ajude Luigi a encontrar sua posição usando no máximo $145$ consultas.

Entrada

A primeira linha contém dois inteiros $n$ e $x$ ( $1 \leq n \leq 5000$ , $1 \leq x \leq 10^9$ ), o tamanho do vetor e o valor que você deve localizar. Garante-se que $x$ aparece em $a$ e que $1 \leq a_i \leq 10^9$ .

Saída

Quando determinar a posição, imprima ! p, onde $p$ é a posição em que $x$ se encontra. Como o vetor é estritamente crescente, essa posição é única.

Notas

As quebras de linha do exemplo servem para melhorar a legibilidade; elas não fazem parte da interação com o juiz.

Este problema é interativo, portanto em alguns momentos é importante que você imprima antes de continuar lendo. Algumas linguagens não imprimem imediatamente ao realizar uma operação de impressão, de modo que é necessário realizar uma operação de flush manualmente:

Python: adicione o parâmetro flush ao imprimir: print(..., flush=True)
C++: use std::cout << std::flush; depois de imprimir.
C: use fflush(stdout); depois de imprimir.
Outras linguagens: consulte a documentação.

Exemplo

Linhas recuadas são do árbitro; as demais, do seu programa.

Exemplo 1