Оказывается, смысл жизни — это перестановка \(p_1, p_2, \ldots, p_n\) целых чисел \(1, 2, \ldots, n\) (\(2 \leq n \leq 100\)). Омкар, создавший все живое, знает эту перестановку и позволит вам выяснить ее с помощью некоторых запросов.
Запрос состоит из массива \(a_1, a_2, \ldots, a_n\) целых чисел от \(1\) до \(n\). \(a\) — это не обязательно перестановка. Омкар сначала вычислит попарную сумму \(a\) и \(p\), то есть вычислит массив \(s\), где \(s_j = p_j + a_j\) для всех \(j = 1, 2, \ldots, n\). Затем он найдет наименьший индекс \(k\) такой, что \(s_k\) встречается в \(s\) более одного раза, и скажет вам \(k\). Если такого индекса \(k\) не существует, то он скажем вам \(0\).
Можно выполнить не более \(2n\) запросов. Выясните смысл жизни \(p\).
Протокол взаимодействия
Начните взаимодействие с чтения одного целого числа \(n\) (\(2 \leq n \leq 100\)) — длины перестановки \(p\).
Затем вы можете делать запросы. Запрос состоит из одной строки «\(? \enspace a_1 \enspace a_2 \enspace \ldots \enspace a_n\)» (\(1 \leq a_j \leq n\)).
Ответом на каждый запрос будет одно целое число \(k\), как описано выше (\(0 \leq k \leq n\)).
После вывода запроса не забудьте вывести перевод строки и сбросить буфер вывода. В противном случае вы получите вердикт Решение «зависло». Для сброса буфера используйте:
- fflush(stdout) или cout.flush() в C++;
- System.out.flush() в Java;
- flush(output) в Pascal;
- stdout.flush() в Python;
- смотрите документацию для других языков.
Чтобы вывести ответ, выведите одну строку «\(! \enspace p_1 \enspace p_2 \enspace \ldots \enspace p_n\)» затем завершите работу.
Вы можете сделать не более \(2n\) запросов. Вывод ответа не считается запросом.
Формат взлома
Для взлома сначала выведите строку, содержащую \(n\) (\(2 \leq n \leq 100\)), затем выведите другую строку, содержащую скрытую перестановку \(p_1, p_2, \ldots, p_n\) чисел от \(1\) до \(n\).
Примечание
В примере скрытая перестановка \(p\) равна \([3, 2, 1, 5, 4]\). Было сделано три запроса.
Первый запрос — \(a = [4, 4, 2, 3, 2]\). Это дает \(s = [3 + 4, 2 + 4, 1 + 2, 5 + 3, 4 + 2] = [7, 6, 3, 8, 6]\). \(6\) — единственное число, которое встречается более одного раза, и впервые оно появляется на индексе \(2\), что делает ответ на запрос \(2\).
Второй запрос — \(a = [3, 5, 1, 5, 5]\). Это дает \(s = [3 + 3, 2 + 5, 1 + 1, 5 + 5, 4 + 5] = [6, 7, 2, 10, 9]\). Здесь нет чисел, которые встречаются более одного раза, поэтому ответ на запрос — \(0\).
Третий запрос — \(a = [5, 2, 4, 3, 1]\). Это дает \(s = [3 + 5, 2 + 2, 1 + 4, 5 + 3, 4 + 1] = [8, 4, 5, 8, 5]\). \(5\) и \(8\) встречаются здесь более одного раза. \(5\) впервые появляется на индексе \(3\), а \(8\) впервые появляется на индексе \(1\), причем \(1 < 3\), что делает ответ на запрос \(1\).
Обратите внимание, что пример приведен только для того, чтобы показать, как работает взаимодействие; не гарантируется, что приведенные выше запросы представляют собой правильную стратегию, с помощью которой можно определить ответ.