E. Сгладить или сконкатенировать
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

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

Во время прокрастинации на работе эльф Дилхан наткнулся на два массива $$$a$$$ и $$$b$$$. Изначально оба массива состоят из одного целого числа $$$2^k$$$ (т.е. $$$a=b=[2^k]$$$), где $$$k$$$ — целое неотрицательное число.

Затем Дилхан применил следующие два типа операций произвольное количество раз (возможно, ноль) в любом порядке:

  1. Сгладить: выберите либо $$$a$$$, либо $$$b$$$, и выберите любой элемент $$$x$$$, который является максимальным в этом массиве ($$$x$$$ не обязательно должен быть максимальным в другом массиве). Затем замените $$$x$$$ на две копии $$$\frac x2$$$ в той же позиции. Эта операция может быть применена, только если $$$x$$$ четное.
  2. Сконкатенировать: сделайте оба массива $$$a$$$ и $$$b$$$ равными $$$a+b$$$, где $$$+$$$ обозначает конкатенацию массивов.

После выполнения этих операций Дилхан выбрасывает $$$b$$$, прячет $$$a$$$ от вас и бросает вам вызов на игру.

Пусть $$$n$$$ — длина скрытого массива $$$a$$$. Вы можете сделать следующий запрос:

  • Выберите интервал $$$[l, r]$$$ ($$$1\le l\le r\le n$$$), и Дилхан скажет вам сумму $$$a_l+a_{l+1}+\cdots+a_r$$$.

Вам нужно определить значение максимального элемента массива $$$a$$$, сделав не более $$$300$$$ запросов.

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

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 100$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

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

Гарантируется, что $$$1\le a_i\le 2^{30}$$$, и массив $$$a$$$ может быть сгенерирован процессом, описанным в условии.

Гарантируется, что сумма значений $$$n$$$ по всем наборам входных данных не превосходит $$$10^5$$$.

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

Для каждого набора входных данных вам сначала дается целое число $$$n$$$ — длина скрытого массива $$$a$$$. Затем вы можете сделать до $$$300$$$ запросов.

Чтобы сделать запрос, выведите строку в следующем формате:

  • $$$\texttt{?}\;l\;r$$$ ($$$1\le l\le r\le n$$$) — индексы, выбранные для запроса.

После того как вы напечатаете запрос, интерактор ответит одним целым числом — суммой $$$a_l+a_{l+1}+\ldots+a_r$$$.

Чтобы сообщить, что вы определили значение максимального элемента массива $$$a$$$, выведите ваш ответ в следующем формате:

  • $$$\texttt{!}\; m$$$ ($$$1\le m\le 2^{30}$$$) — значение максимального элемента.

Вывод ответа не считается одним из $$$300$$$ запросов.

После вывода ответа переходите к следующему набору входных данных. Если текущий набор входных данных является последним, завершите программу.

После вывода каждого запроса не забудьте вывести перевод строки и сбросить буфер вывода$$$^{\text{∗}}$$$. В противном случае вы получите вердикт Решение «зависло».

На любом шаге взаимодействия, если вы считали $$$-1$$$ вместо корректных данных, ваше решение должно немедленно завершиться. Это означает, что ваше решение получит вердикт Неправильный ответ из-за некорректного запроса или любой другой ошибки. Если программа не завершится, вы можете получить любой вердикт, так как ваша программа продолжит чтение из закрытого потока.

Интерактор в этой задаче не адаптивен. Другими словами, массив $$$a$$$ фиксирован до любых запросов и не изменится в процессе взаимодействия.

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

$$$^{\text{∗}}$$$Чтобы сбросить буфер вывода, используйте:

  • fflush(stdout) или cout.flush() в C++;
  • sys.stdout.flush() в Python;
  • смотрите документацию для других языков.
Пример
Входные данные
4
11

9

4

12

1

1

8

4

4

4

4

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


? 3 8

? 1 4

? 5 11

! 2

? 1 1

! 1

? 1 1

? 2 2

? 3 3

? 4 4

! 4

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

В первом наборе входных данных скрытый массив Дилхана $$$a$$$ равен $$$[1, 1, 1, 1, 2, 2, 2, 1, 1, 2, 2]$$$. Он может быть сгенерирован следующим образом:

#Тип$$$a$$$ после операции$$$b$$$ после операции
0$$$[4]$$$$$$[4]$$$
1Сгладить $$$a$$$$$$[\underline 4] \to {[2, 2]}$$$$$$[4]$$$
2Сгладить $$$b$$$$$$[2, 2]$$$$$$[\underline 4] \to {[2, 2]}$$$
3Сгладить $$$a$$$$$$[2, \underline 2] \to {[2, 1, 1]}$$$$$$[2, 2]$$$
4Сконкатенировать$$$[2, 1, 1, 2, 2]$$$$$$[2, 1, 1, 2, 2]$$$
5Сгладить $$$a$$$$$$[\underline 2, 1, 1, 2, 2]\to {[1, 1, 1, 1, 2, 2]}$$$$$$[2, 1, 1, 2, 2]$$$
6Сконкатенировать$$$[1, 1, 1, 1, 2, 2, 2, 1, 1, 2, 2]$$$$$$[1, 1, 1, 1, 2, 2, 2, 1, 1, 2, 2]$$$
  • Для запроса $$$\mathtt{?\;3\;8}$$$ жюри ответило $$$1+1+2+2+2+1=9$$$;
  • Для запроса $$$\mathtt{?\;1\;4}$$$ жюри ответило $$$1+1+1+1=4$$$;
  • Для запроса $$$\mathtt{?\;5\;11}$$$ жюри ответило $$$2+2+2+1+1+2+2=12$$$.

И значение максимального элемента массива $$$a$$$ равно $$$2$$$.

Во втором наборе входных данных массив $$$a$$$ содержит только один элемент. По запросу значение единственного элемента равно $$$1$$$, и оно также должно быть максимальным значением.

В третьем наборе входных данных скрытый массив Дилхана $$$a$$$ равен $$$[4, 4, 4, 4, 4, 4, 4, 4]$$$. Он может быть сгенерирован следующим образом:

#Тип$$$a$$$ после операции$$$b$$$ после операции
0$$$[4]$$$$$$[4]$$$
1Сконкатенировать$$$[4, 4]$$$$$$[4, 4]$$$
2Сконкатенировать$$$[4, 4, 4, 4]$$$$$$[4, 4, 4, 4]$$$
3Сконкатенировать$$$[4, 4, 4, 4, 4, 4, 4, 4]$$$$$$[4, 4, 4, 4, 4, 4, 4, 4]$$$

И значение максимального элемента массива $$$a$$$ равно $$$4$$$.

В четвертом наборе входных данных скрытый массив Дилхана $$$a$$$ равен $$$[2^{29}, 2^{29}, 2^{30}, 2^{29}, 2^{28}, 2^{28}, 2^{29}, 2^{29}]$$$.