Problem B
Staring Contest

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

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

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

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

Взаємодія

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

Ваше рішення вважається правильним, якщо $b_i=a_i$ для кожного спортсмена $i$, окрім одного, якого Ви можете недооцінити. Для точності ми вимагаємо, щоб $b_i\le a_i$ для всіх $1\le i\le n$ та дозволяємо $b_k\ne a_k$ не більше ніж для одного $k$.

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

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

Кількість спортсменів $n$ задовольняє умову $2\le n\le 1500$. Навички кожного спортсмена $a_i$ задовольняють умову $1\le a_i\le 86400$, вони всі різні. Ви можете використовувати не більше 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