Це інтерактивна задача.
Загадана деяка перестановка p чисел від 1 до n, де n парне. Ви можете задавати запити наступного вигляду:
Для даного набору різних індексів непарної довжини a1,a2,…,al, ви можете дізнатись таке число x, що px є медіаною елементів pa1,pa2,…,pal.
Відомо, що p1<pn. Вгадайте перестановку p за не більше ніж 23n запитів.
Гарантується, що перестановка зафіксована перед початком взаємодії. Іншими словами, інтерактор не адаптивний.
Нагадаємо, що медіана непарної кількості чисел визначається наступним чином:
Нехай b1,b2,…,b2k+1 — це ці числа в порядку зростання (де 2k+1 — кількість чисел). Тоді медіаною є число bk+1.
Почніть взаємодію, зчитавши одне ціле число n (2≤n≤1000, n парне) — довжину перестановки.
Щоб задати питання, необхідно вивести в одному рядку спочатку символ «?
», потім ціле число l, а потім l цілих чисел ai (1≤l≤n, 1≤ai≤n, l непарне, всі ai попарно різні) — індекси, для яких необхідно знайти медіану.
У відповідь програма журі виведе таке число x, що px є медіаною елементів pa1,pa2,…,pal.
Коли ви визначили перестановку, то виведіть спочатку символ «!
», а потім n чисел p1,p2,…,pn. Після цього ваша програма має завершити роботу.
Після кожного запиту і виводу відповіді не забудьте вивести перехід рядка і скинути буфер виводу. Для скидання буферу використовуйте:
fflush(stdout)
чи cout.flush()
в C++;
System.out.flush()
в Java;
flush(output)
в Pascal;
stdout.flush()
в Python;
В прикладі загадана перестановка p=(1,3,2,4).
Перший запит в прикладі — хочемо дізнатись медіану елементів p2,p3,p4, що дорівнюють 3,2,4 відповідно. Медіана цих чисел — 3, тобто p2, тому інтерактор відповідає числом 2.
Другий запит в прикладі — хочемо дізнатись медіану елементів p1,p3,p4, що дорівнюють 1,2,4 відповідно. Медіана цих чисел — 2, тобто p3, тому інтерактор відповідає числом 3.
Третій запит в прикладі — хочемо дізнатись медіану елементів p1,p2,p4, що дорівнюють 1,3,4 відповідно. Медіана цих чисел — 3, тобто p2, тому інтерактор відповідає числом 2.
Четвертий запит в прикладі — хочемо дізнатись медіану елементів p1,p2,p3, що дорівнюють 1,3,2 відповідно. Медіана цих чисел — 2, тобто p3, тому інтерактор відповідає числом 3.