409460: GYM103566 H Дорога в школу.

H. Дорога в школу.ограничение по времени на тест1 секундаограничение по памяти на тест256 мегабайтвводстандартный вводвыводстандартный вывод

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

В центре города Глубокоозёрный находится круглое и глубокое озеро. Вокруг озера проложена кольцевая дорога, которая представляет из себя окружность. Вдоль дороги расположены $$$n$$$ домов таким образом, что расстояние между соседними домами составляет ровно один километр. Все дома пронумерованы последовательно числами от $$$1$$$ до $$$n$$$, то есть дома $$$i$$$ и $$$i + 1$$$ являются соседними при $$$1 \le i < n$$$, а также дома $$$n$$$ и $$$1$$$ являются соседними. В одном из домов располагается единственная в городе школа, а еще в одном из домов живет мальчик Пахом. Каждый будний день Пахом ходит из дома в школу вдоль дороги по кратчайшему пути (если такой путь не единственный, то Пахом выбирает любой из кратчайших путей), пусть длина этого пути равна $$$len$$$ километров. Можно заметить, что всего есть два возможных пути из дома Пахома в школу, так как улица только одна и представляет из себя окружность.

Иногда в городе меняют асфальт на дороге и в таком случае дорогу перекрывают на участке между двумя соседними домами. Причем перекрытым может быть только один участок, чтобы из любого дома можно было дойти до любого другого дома по дороге. Участки дороги пронумерованы таким образом, что участок между домами $$$i$$$ и $$$i + 1$$$ имеет номер $$$i$$$ ($$$1 \le i < n$$$), а участок между домами $$$n$$$ и $$$1$$$ имеет номер $$$n$$$.

Можно заметить, что если один участок дороги перекрыт, то остается единственный путь из дома Пахома в школу, вне зависимости от того какой именно участок перекрыт. В таком случае Пахом идет этим единственным путем. Этот путь может оказаться длиннее чем $$$len$$$ километров, поэтому Пахом не очень любит, когда в его городе меняют асфальт.

Ваша задача состоит в том, чтобы определить длину $$$len$$$. Для этого вы можете сделать не более трех запросов первого типа:

$$$?$$$ $$$i$$$ ($$$1 \le i \le n$$$) — узнать длину пути от дома Пахома до школы в случае, если перекрыт участок дороги номер $$$i$$$.

После этого следует вывести запрос второго типа, который сообщает ответ на задачу:

$$$!$$$ $$$len$$$

После этого запроса необходимо завершить программу.

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

Первая строка входных данных содержит целое число $$$n$$$ ($$$3 \le n \le 10^5$$$) — количество домов в городе.

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

Чтобы вывести ответ на задачу, выведите его в формате $$$!$$$ $$$len$$$, где $$$len$$$ — длина кратчайшего пути из дома Пахома в школу при условии, что ни один из участков дороги не перекрыт.

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

Чтобы задать запрос первого типа, выведите $$$?$$$ $$$i$$$ ($$$1 \le i \le n$$$), где $$$i$$$ — номер участка дороги, который вы хотите перекрыть. После вывода запроса необходимо $$$\textbf{вывести перевод строки}$$$ и сделать операцию $$$\textbf{«flush»}$$$.

После каждого запроса типа $$$?$$$ считайте одно целое число $$$val$$$ — длину пути из дома Пахома в школу при условии, что перекрыт участок дороги с номером $$$i$$$.

Обратите внимание, что вы можете сделать не более 3 запросов типа $$$?$$$.

Чтобы сообщить, что ответ найден, требуется вывести $$$!$$$ $$$len$$$, где $$$len$$$ — длина кратчайшего пути из дома Пахома в школу при условии, что ни один из участков дороги не перекрыт. После этого требуется сделать «flush» и завершить программу.

Запрос на вывод ответа не входит в ограничение на 3 запроса.

Для сброса буфера вывода (то есть для операции «flush») сразу после вывода нужно сделать:

• C++: endl одновременно и делает перевод строки, и «flush»;

  Другие варианты: cout.flush(), cout « flush.

• Java: System.out.println() одновременно и делает перевод строки, и «flush».

  Если вы используете не System.out, то используйте команду flush вашего потока вывода.

• Python: print одновременно и делает перевод строки, и «flush»;

  Напрямую можно сделать «flush» с помощью sys.stdout.flush() (требует import sys).

• Pascal: Выполните flush(output) после вывода через writeln.

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

3

2

1

1

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

? 1

? 2

? 3

! 1

Примечание

В тестовом примере показано, как программа взаимодействует с проверяющей системой.

Сначала программа считывает значение $$$n$$$, которое равно трем.

Далее программа задает запрос первого типа $$$?$$$ $$$1$$$ (перекрыли участок дороги $$$1$$$ между домами $$$1$$$ и $$$2$$$), а затем считывает число $$$2$$$ — ответ на этот запрос.

Далее программа задает запрос первого типа $$$?$$$ $$$2$$$ (перекрыли участок дороги $$$2$$$ между домами $$$2$$$ и $$$3$$$), а затем считывает число $$$1$$$ — ответ на этот запрос.

Далее программа задает запрос первого типа $$$?$$$ $$$3$$$ (перекрыли участок дороги $$$3$$$ между домами $$$3$$$ и $$$1$$$), а затем считывает число $$$1$$$ — ответ на этот запрос.

И в конце программа выводит ответ на задачу в виде $$$!$$$ $$$1$$$ и завершает свою работу.

Почему ответ в данном случае равен $$$1$$$? Давайте посмотрим, что мы узнали из запросов. Если перекрыть участок дороги $$$1$$$, то путь будет иметь длину $$$2$$$, а если перекрыть участок дороги $$$2$$$ или $$$3$$$, то путь будет иметь длину $$$1$$$. Из этого можно сделать вывод, что путь из дома Пахома в школу состоит из участка $$$1$$$ и имеет длину $$$1$$$.