Задача . E. Арифметическая прогрессия

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

Арифметическая прогрессия — такая последовательность целых чисел, что разность каждого элемента и предшествующего ему (\(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\)) — элементы списка.

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