E. Арифметическая прогрессия
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

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

Арифметическая прогрессия — такая последовательность целых чисел, что разность каждого элемента и предшествующего ему ($$$x_i - x_{i - 1}$$$, где $$$i \ge 2$$$) постоянна (это значение называется разностью арифметической прогрессии).

Тем самым, арифметическая прогрессия — последовательность вида $$$x_i = x_1 + (i - 1) d$$$, где $$$d$$$ — разность арифметической прогрессии.

Загадан список из $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$.

Гарантируется, что все элементы $$$a_1, a_2, \ldots, a_n$$$ лежат в диапазоне от $$$0$$$ до $$$10^9$$$, включительно.

Этот список особенный: если отсортировать его в возрастающем порядке, то он превратится в арифметическую прогрессию с положительной разностью ($$$d > 0$$$). Например, список $$$[14, 24, 9, 19]$$$ удовлетворяет этому условию, так как после сортировки он становится равен $$$[9, 14, 19, 24]$$$, что может быть получено с помощью $$$x_n = 9 + 5 \cdot (n - 1)$$$.

Вместе со списком, у вас есть устройство с практически разряженной батареей, которым вы можете воспользоваться, чтобы выполнить не более $$$60$$$ запросов следующих двух видов:

  • Вы называете значение $$$i$$$ ($$$1 \le i \le n$$$), а устройство отображает значение $$$a_i$$$.
  • Вы называете значение $$$x$$$ ($$$0 \le x \le 10^9$$$), а устройство отображает $$$1$$$, если есть элемент со значением строго больше $$$x$$$, и отображает $$$0$$$ иначе.

Вы можете использовать это устройство, чтобы задать не более $$$60$$$ запросов. Ваша задача — узнать наименьший элемент и разность заданной арифметической прогрессии, то есть значения $$$x_1$$$ и $$$d$$$ из ее определения. Обратите внимание, что список $$$a$$$ не упорядочен по возрастанию.

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

Взаимодействие начинается с одного целого числа $$$n$$$ ($$$2 \le n \le 10^6$$$), количества элементов в списке.

Затем вы можете делать запросы двух видов:

  • "? i" ($$$1 \le i \le n$$$) — чтобы узнать значение $$$a_i$$$.
  • "> x" ($$$0 \le x \le 10^9$$$) — чтобы проверить есть ли элемент больший $$$x$$$.

После вывода запроса, считайте ответ $$$r$$$ на него как целое число.

  • Для запроса первого типа, $$$r$$$ удовлетворяет $$$0 \le r \le 10^9$$$.
  • Для запроса второго типа, $$$r$$$ равен $$$0$$$ или $$$1$$$.
  • В случае, если вы сделаете более $$$60$$$ запросов или нарушите ограничения на числа в запросе, то в ответ вы получите $$$r = -1$$$.
  • Если ваша программа завершится после получения -1, то вы получите вердикт «Неправильный ответ». В противном случае, вердикт может быть любым, так как ваша програма продолжит читать из закрытого потока.

После того как вы выясните значение наименьшего элемента ($$$x_1$$$) и разность прогрессии ($$$d$$$), выведите:

  • "! $$$x_1$$$ $$$d$$$"

И завершите программу после этого. Этот запрос не учитывается относительно ограничения в $$$60$$$ запросов.

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

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

Hacks

Для взломов используйте следующий формат:

Первая строка должна содержать одно целое число $$$n$$$ ($$$2 \le n \le 10^6$$$) — количество элементов в списке.

Вторая строка должна содержать $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i \le 10^9$$$) — элементы списка.

Также после сортировки списка по возрастанию, он должен образовывать арифметическую прогрессию с положительной разностью.

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

0

1

14

24

9

19

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

> 25

> 15

? 1

? 2

? 3

? 4

! 9 5
Примечание

Обратите внимание, что взаимодействие в примере содержит пустые строки только для наглядности. В настоящем взаимодействии нет пустых строк, и вы тоже не должны их выводить.

Список в примере равен $$$[14, 24, 9, 19]$$$.