Точки на прямій

Це інтерактивна задача.

Є $n$ точок на числовій прямій, що мають цілі координати $x_1,x_2,\dots ,x_n$. Гарантується, що $1\le x_i\le n$ для $1\le i\le n$.

Вважається, що точка $x_k$ знаходиться між точками $x_i$ та $x_j$ тоді й тільки тоді, коли вона належить відрізку, побудованому на точках $x_i$ та $x_j$. Формально точка $x_k$ знаходиться між точками $x_i$ та $x_j$ тоді й тільки тоді, коли $x_i\le x_k\le x_j$ або $x_j\le x_k\le x_i$.

Вам потрібно знайти будь-які два індекси $i$ та $j$ такі, що всі $n$ точок знаходяться між точками $x_i$ та $x_j$.

Ви можете користуватися наступним запитом: вибрати три індекси ($i$, $j$, $k$) та дізнатись, чи знаходиться точка $x_k$ між точками $x_i$ та $x_j$.

Вам дозволяється використати не більше ніж $22222$ запитів.

Гарантується, що координати точок зафіксовані перед початком взаємодії. Іншими словами, інтерактор не є адаптивним.

Вхідні дані

У першому рядку задано одне ціле число $n$ ($3\le n\le 2\cdot 10^4$) — кількість точок.

Протокол взаємодії

Для виконання запиту потрібно вивести «? $i$ $j$ $k$» ($1\le i,j,k\le n$), після чого виведіть символ кінця рядка та виконайте операцію flush.

У відповідь на запит програма журі виведе одне ціле число $f$ ($f\in \{0,1\}$). Якщо $f=1$, то точка $x_k$ знаходиться між точками $x_i$ та $x_j$; якщо $f=0$, то точка $x_k$ не знаходиться між ними.

Якщо запит невалідний (тобто перевищено максимальну кількість запитів або параметри запиту є невалідними), то програма журі виведе -1 та припинить роботу. У такому випадку завершіть роботу програми, щоб отримати вердикт Неправильна відповідь.

Коли ви будете готові надати відповідь, виведіть її у форматі «! $i$ $j$» ($1\le i,j\le n$), де $i$ та $j$ — шукані індекси точок. Після цього завершіть роботу програми.

Операція flush виконується наступним чином:

• fflush(stdout) або cout.flush() в C++;

• System.out.flush() в Java;

• flush(output) в Pascal;

• sys.stdout.flush() в Python.

Приклади

4

1

1

? 1 4 2

? 1 4 3

! 1 4

Примітка

У прикладі точки мають координати $x=[1,2,3,4]$.

Оцінювання

1. ($17$ балів): $n\le 20$;

2. ($16$ балів): $n\le 100$;

3. ($30$ балів): $n\le 10000$;

4. ($23$ бали): $n\le 20000$, $x_i\le 2$;

5. ($10$ балів): $n\le 12000$;

6. ($4$ бали): без додаткових обмежень.