Problem B
Staring Contest

Змагання у триманні погляду — це класична битва за невразливість, в якій двоє людей дивляться один на одного в очі, зберігаючи обличчя впевненої безтурботності. Мета полягає в тому, щоб тримати зоровий контакт довше, ніж опонент. Змагання закінчується, коли один учасник втрачає самовладання, зазвичай, зводячи погляд, посміхаючись, говорячи або хихотячи.

Як тренер збірної команди з тримання погляду, вам потрібно визначити невразливість кожного з $n$ членів Вашої команди на майбутніх світових фіналах. $i$-тий спортсмен може тримати очний контакт рівно $a_ i$ секунд, але ці значення на початку Вам не відомі. Наприклад, у Вас може бути команда з $n=3$ членів:

Коли спортсмени $i$ та $j$ змагаються, конфронтація триває рівно $\min (a_ i, a_ j)$ секунд, після чого слабший суперник втрачає самовладання, і обидва учасники відразу ж починають посміхатися та хихотіти. Наприклад, якщо Анна змагається проти Естер, змагання триває 431 секунду. Важливо підкреслити, що для стороннього спостерігача справжнього переможця конфронтації (у цьому випадку — Естер) визначити неможливо. Можливо лише виміряти тривалість змагання.

Ваша мета — оцінити значення $a_1, \ldots , a_ n$ за допомогою якомога меншої кількості змагань з тримань погляду. Як зрозуміло, сила найсильнішого спортсмена ніколи не може бути визначена, тому Ви можете недооцінити одне зі значень $a_ i$.

Взаємодія

Це інтерактивна задача. Взаємодія починається з того, що Ви отримуєте один рядок з цілим числом $n$. Далі Ви можете запитувати значення, виконуючи запити у вигляді “? $i$ $j$”, де $1\leq i\leq n$, $1\leq j\leq n$ та $i\neq j$. Відповідь на запит — це ціле число: значення $\min (a_ i, a_ j)$. Взаємодія закінчується тоді, коли Ви виводите на екран рядок, що складається з ! та $n$ оцінок у вигляді цілих чисел $b_1$, $\ldots $, $b_ n$, розділених пробілами. Це має бути вашим останнім рядком виводу.

Ваше рішення вважається правильним, якщо $b_ i=a_ i$ для кожного спортсмена $i$, окрім одного, якого Ви можете недооцінити. Для точності ми вимагаємо, щоб $b_ i\leq a_ i$ для всіх $1\leq i\leq n$ та дозволяємо $b_ k \neq a_ k$ не більше ніж для одного $k$.

Взаємодія відбувається з незмінним інтерактором, що означає, що значення $a_1, \ldots , a_ n$ визначаються до початку взаємодії.

Обмеження та оцінювання

Кількість спортсменів $n$ задовольняє умову $2\leq n\leq 1500$. Навички кожного спортсмена $a_ i$ задовольняють умову $1\leq a_ i\leq 86\, 400$, вони всі різні. Ви можете використовувати не більше 3000 запитів; останній рядок виводу, тобто рядок, що починається з символу !, не рахується як запит.

Ваше рішення буде перевірено на наборі тестових груп, кожна з яких оцінюється в певну кількість балів. Кожна група тестів містить набір тестових випадків. Щоб отримати бали за групу тестів, вам потрібно вирішити всі тестові випадки у групі. Остаточний бал складається з максимального балу, отриманий за одне подання.

Для групи $3$, Ваш бал буде мінімальним балом серед всіх тестових випадків у групі. Бали за кожен тестовий випадок залежать від кількості запитів, які ви використовуєте; менша кількість запитів оцінюється краще: Припустимо, що ви використали $q$ запитів. Якщо $q \le n+25$, то ви отримуєте повний бал в $80$ балів. Якщо $q > 3000$, то ви не отримуєте жодного балу. В іншому випадку, ви отримуєте $118.2 - 12 \cdot \ln (q - n)$ балів, округлених до найближчого цілого числа. Наприклад, для $n = 1500$ та $q = 3000$, ви отримуєте $30$ балів.

Пояснення до прикладу взаємодії

Приклад взаємодії $1$ показує можливу взаємодію згідно з вищезазначеним прикладом. Зверніть увагу, що сила Анни та Тоні визначені коректно. (Сила Естер ніколи не може бути визначена.)

3

? 1 2

431

? 1 3

121

? 3 2

121

! 431 431 121