L. Одинокое число

Это интерактивная задача.

Маша записала $N$ целых чисел в неубывающем порядке: $a_1 \le a_2 \le \ldots \le a_N$. Среди них есть число $C$, которое встречается ровно один раз, а все остальные встречаются ровно два раза.

Найдите «одинокое» число $C$, попросив Машу назвать не более 42 раз число по его номеру. Известно, что $1 \le a_i \le 10^9$.

В начале решение должно считать число $N$ ($1 \le N \le 10^6$).

Затем можно сделать не более 42 запросов вида ? i ($1 \le i \le N$). Ответом является число $a_i$.

Чтобы вывести ответ, выведите ! C и немедленно завершите работу.

После каждого запроса, в том числе после вывода ответа, выполняйте flush.

Ответ выводится запросом вида ! C.