Задача . C. Шоколадный заяц

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

Мы загадали перестановку \(p\) длины \(n\) из элементов от \(1\) до \(n\). Вам надо ее отгадать. Чтобы это сделать, вы можете сказать нам 2 различных индекса \(i\) и \(j\), и мы вам скажем, чему равняется \(p_{i} \bmod p_{j}\) (остаток от деления \(p_{i}\) на \(p_{j}\)).

У нас хватит терпения на то, чтобы ответить на \(2 \cdot n\) запросов; вам нужно уложиться в это ограничение. Сможете ли вы это сделать?

Напомним, что перестановка длины \(n\) — это массив, состоящий из \(n\) различных целых чисел от \(1\) до \(n\) в произвольном порядке. Например, \([2,3,1,5,4]\) — это перестановка, но \([1,2,2]\) — это не перестановка (\(2\) встречается дважды в массиве), а \([1,3,4]\) также не является перестановкой (\(n=3\), но в массиве встречается \(4\)).

Взаимодействие начинается с чтения числа \(n\).

Далее вы можете задать максимум \(2 \cdot n\) запросов следующего вида:

• «? x y» (\(1 \le x, y \le n, x \ne y\)).

После каждого запроса вам необходимо считать целое число \(k\), равное \(p_x \bmod p_y\).

Когда вы отгадаете перестановку, выведите в одной строку «! » (без кавычек) и массив \(p\), после чего завершите работу.

После вывода запроса не забудьте вывести перевод строки и сбросить буфер вывода. В противном случае вы получите вердикт Решение «зависло». Для сброса буфера используйте:

• fflush(stdout) или cout.flush() в C++;
• System.out.flush() в Java;
• flush(output) в Pascal;
• stdout.flush() в Python;
• смотрите документацию для других языков.

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

Формат взломов

В первой строке выведите \(n\) (\(1 \le n \le 10^4\)). Во второй строке выведите перестановку из \(n\) чисел \(p_1, p_2, \ldots, p_n\).