C. Контакт
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Земля наконец-то установила контакт с инопланетной цивилизацией, которая посылает сообщения через радиосигнал. Началось всё с объёмного сообщения, в котором объяснялись фундаментальные вещи логики, математики, физики и других наук, например, что такое целое число.

Позже было разъяснено, что такое перестановка — последовательность P из N целых различных чисел, каждое из которых лежит в диапазоне от 1 до N. А также, что такое инверсии в последовательности a — это количество таких i и j, что 1 ≤ i < j ≤ N и ai > aj.

Чтобы проверить, насколько примитивна наша цивилизация, внеземляне решили загадать перестановку размера N, которую мы должны отгадать по средством общения. Мы можем задавать лишь один тип вопроса, на который они нам отвечают. А именно, мы можем выбрать множество различных чисел от 1 до N, передать их, а в ответ получить количество инверсий в последовательности полученной из перестановки удалением всех чисел, кроме выбранных. Порядок оставшихся чисел при этом не меняется.

Например, пусть была загадана перестановка (3, 6, 1, 4, 5, 2) и нас интересует ответ на набор чисел {2, 3, 4}. Если оставить только эти числа, выйдет (3, 4, 2), и ответом будет 2 — именно столько инверсий содержится в новой последовательности.

Обратите внимание, что перестановка не меняется после ответа на вопрос.

К сожалению, общение в космосе является очень утомительным по времени занятием, особенно когда собеседник находится в системе Веги, что почти в 26-и световых годах от нас. Поэтому суммарное количество выбранных чисел для вопросов ограничено в 40 000.

Помогите нашей цивилизации пройти экзамен, отгадайте перестановку!

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

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

В начале вам на ввод подаётся целое число N — размер перестановки (1 ≤ N ≤ 1000).

Далее ваша программа общается с программой жюри. Вы можете выводить запрос на количество инверсий в формате «? k t1 t2 ... tk», где ti и есть выбранные числа. Каждый такой запрос должен быть в отдельной строке и заканчиваться очисткой буфера вывода.

Если запрос был корректным, следом вам на ввод в отдельной строке будет подано целое число — ответ на этот запрос.

Если вы считаете, что отгадали перестановку, следует вывести её в отдельной строке в формате «! P1 P2 ... PN», разделяя числа пробелами. После этого ваша программа должна немедленно завершиться.

Пример
Входные данные
4
3
0
Выходные данные
? 4 1 2 3 4
? 2 1 2
! 1 4 3 2
Примечание

Для очистки буфера вывода в различных языках используются следующие команды:

  • В языке Pascal: flush(output);
  • В С/С++: fflush(stdout) или cout.flush();
  • В Java: System.out.flush();
  • В Python: sys.stdout.flush() из библиотеки sys;
  • В C#: Console.Out.Flush();