Căutare Binară Interactivă

Cerință

Aceasta este o problemă interactivă. Soluția ta va comunica cu un program al comisiei pentru a găsi un număr secret $X$, cuprins între $1$ și $1000$. Programul tău va interacționa în felul următor:

• Interogare: Programul tău va afișa pe ecran ? $Y$. Acum programul va citi răspunsul oferit de programul comisiei. Dacă ce s-a citit este $1$, atunci $Y \leq X$, altfel $X < Y$. Se vor face maximum $10$ interogări.
• Răspuns: Programul tău va afișa pe ecran ! $Y$. După ce ai afișat răspunsul, programul tău trebuie să-și încheie execuția.

Restricții și precizări

• $1 \leq X \leq 1000$

Exemplu de interacțiune

Consolă

? 5
1
? 6
2
! 5