Рэй потерял свой массив и должен найти его, спросив Омкара. Омкар готов раскрыть, что массив обладает следующими качествами:
- Массив содержит \(n\) (\(1 \le n \le 2 \cdot 10^5\)) элементов.
- Каждый элемент в массиве \(a_i\) является целым числом в диапазоне \(1 \le a_i \le 10^9.\)
- Массив отсортирован в порядке неубывания.
Рэй может отправить Омкару серию запросов. Запрос состоит из двух целых чисел, \(l\) и \(r\), таких, что \(1 \le l \le r \le n\). Омкар ответит двумя целыми числами, \(x\) и \(f\). \(x\) — мода подмассива от индекса \(l\) до индекса \(r\) включительно. Модой массива называют число, которое встречается в нем чаще всего. Если есть несколько чисел, которые встречаются наибольшее количество раз, модой считается наименьшее из них. \(f\) — это количество раз, которое \(x\) встречается в запрашиваемом подмассиве.
Массив имеет \(k\) (\(1 \le k \le \min(25000,n)\)) различных элементов. Однако из-за грехов Рэя Омкар не скажет Рэю, чему равно \(k\). Рэю разрешено отправить не более \(4k\) запросов.
Помогите Рэю найти его потерянный массив.
Протокол взаимодействия
Взаимодействие начинается с чтения \(n\).
Затем вы можете сделать один тип запроса:
- "\(? \enspace l \enspace r\)" (\(1 \le l \le r \le n\)) где \(l\) и \(r\) это границы подмассива, который вы хотите запросить.
Ответ на каждый запрос будет иметь вид "\(x \enspace f\)", где \(x\) — это мода подмассива, а \(f\) — количество раз, которое \(x\) встречается в подмассиве.
- \(x\) удовлетворяет (\(1 \leq x \leq 10^9\)).
- \(f\) удовлетворяет (\(1 \leq f \leq r-l+1\)).
- Если вы делаете более \(4k\) запросов или нарушаете диапазон номеров в запросе, вы получите вывод "-1."
- Если вы прекратите работу после получения ответа "\(-1\)", вы получите вердикт "Неправильный ответ ". В противном случае вы можете получить произвольный вердикт, потому что ваше решение будет продолжать читать из закрытого потока.
Чтобы вывести ответ, выведите:
- "\(! \enspace a_1 \enspace a_2 \enspace \ldots \enspace a_{n-1} \enspace a_n\)", который является восклицательным знаком, за которым следует массив с пробелом между каждым элементом.
После этого завершите программу. Этот запрос не учитывается в лимит запросов \(4k\).
После вывода запроса не забудьте вывести перевод строки, и сбросить буфер вывода. В противном случае вы получите вердикт Решение «зависло». Для сброса буфера используйте:
- fflush(stdout) или cout.flush() в C++;
- System.out.flush() в Java;
- flush(output) в Pascal;
- stdout.flush() в Python;
- смотрите документацию для других языков.
Формат взломов
Для взлома выведите \(1\) целое число в первой строке: \(n\) (\(1 \le n \le 2 \cdot 10^5\)). Во второй строке выведите \(n\) целых чисел \(a_1, a_2, \ldots, a_{n-1}, a_n\), разделенных пробелами. Среди них должно быть не более \(25000\) различных чисел и \(a_j \le a_{j+1}\) должно выполняться для всех \(j\) от \(1\) до \(n-1\).
Примечание
Первый запрос: \(l=1\) и \(r=6\). Мода равна \(2\), а \(2\) встречается \(2\) раза, поэтому \(x=2\) и \(f=2\). Обратите внимание, что \(3\) также встречается два раза, но выводится \(2\), потому что \(2\) меньше.
Второй запрос: \(l=1\) и \(r=3\). Мода равна \(2\) и \(2\) встречается дважды в подмассиве с границами \([1,3]\).
Третий запрос: \(l=4\) и \(r=6\). Мода равна \(3\) и \(3\) встречается дважды в подмассиве с границами \([4,6]\).
Четвертый запрос: \(l=3\) и \(r=4\). Мода равна \(2\), и встречается один раз в подмассиве с границами \([3,4]\). Обратите внимание, что \(3\) также встречается всего один раз в этом диапазоне, но \(2\) меньше, чем \(3\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
6
2 2
2 2
3 2
2 1
|
? 1 6
? 1 3
? 4 6
? 3 4
! 1 2 2 3 3 4
|