G. Угадайте центроид
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

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

Есть загаданное дерево, состоящее из $$$n$$$ вершин, которое имеет только один центроид. Сначала вам известно только $$$n$$$, и ваша задача  — найти центроид дерева.

Вы можете спросить расстояние между любыми двумя вершинами не более $$$2\cdot10^5$$$ раз.

Обратите внимание, что интерактор является неадаптивным. То есть, дерево фиксировано в каждом тесте заранее и не зависит от ваших запросов.

Вершина называется центроидом, если ее удаление разбивает дерево на поддеревья, в каждом из которых не более $$$\lfloor\frac{n}{2}\rfloor$$$ вершин.

Входные данные

Единственная строка ввода содержит целое число $$$n$$$ ($$$3\le n\le 7.5\cdot10^4$$$) — количество вершин в дереве.

Протокол взаимодействия

Начните взаимодействие с чтения $$$n$$$.

Чтобы задать запрос о расстоянии между двумя вершинами $$$u, v$$$ ($$$1 \le u, v \le n$$$), выведите «? u v».

Если вы определили, что центроидом дерева является $$$x$$$, используйте «! x» для вывода ответа.

После вывода запроса не забудьте вывести конец строки и сбросить буфер вывода. В противном случае вы получите Решение «зависло». Для этого используйте:

  • fflush(stdout) или cout.flush() в C++;
  • System.out.flush() в Java;
  • flush(output) в Pascal;
  • stdout.flush() в Python;
  • см. документацию для других языков.

В этой задаче взломы отключены.

Гарантируется, что в этой задаче есть не более $$$500$$$ тестов.

Пример
Входные данные
5

2

1

2

3

1

1

1
Выходные данные

? 1 2

? 1 3

? 1 4

? 1 5

? 2 3

? 3 4

? 4 5

! 3
Примечание

Вот изображение дерева из примера.