Это интерактивная задача.
Загадана перестановка \(p\) чисел \([0,1,2,\ldots,n-1]\). Ваша задача — найти \(2\) индекса \(x\) и \(y\) (\(1 \leq x, y \leq n\), возможно, \(x=y\)) такие, что \(p_x=0\) или \(p_y=0\). Чтобы это сделать, вы можете сделать не более чем \(2n\) запросов.
В каждом запросе вы даете два целых числа \(i\) и \(j\) (\(1 \leq i, j \leq n\), \(i \neq j\)) и получаете значение \(\gcd(p_i,p_j)^\dagger\).
Обратите внимание, что перестановка \(p\) зафиксирована до начала взаимодействия, и не зависит от ваших запросов.
\(^\dagger\) \(\gcd(x, y)\) обозначает наибольший общий делитель (НОД) чисел \(x\) и \(y\). Обратите внимание, что \(\gcd(x,0)=\gcd(0,x)=x\) для всех положительных целых чисел \(x\).
Протокол взаимодействия
Взаимодействие начинается для каждого набора входных данных после считывания числа \(n\).
Чтобы сделать запрос, выведите «? \(i\) \(j\)» (\(1 \leq i, j \leq n\), \(i \neq j\)) без кавычек. После этого считайте одно целое число — ответ на ваш запрос \(\gcd(p_i,p_j)\). Вы можете сделать не более чем \(2n\) таких запросов в каждом наборе входных данных.
Если вы знаете ответ, выведите «! \(x\) \(y\)» (\(1 \leq x, y \leq n\)) без кавычек. После этого считайте целое число \(1\) или \(-1\). Если \(p_x=0\) или \(p_y=0\), вы получите \(1\), иначе вы получите \(-1\). Если вы получили \(-1\), ваша программа должна немедленно завершиться, чтобы получить вердикт Неправильный ответ. В противном случае вы можете получить любой вердикт, так как программа продолжит чтение из закрытого потока.
Если вы получили число \(-1\) вместо ответа или корректного значения \(n\), то ваша программа сделала некорректный запрос, превысила число запросов, или дала неправильны ответ на предыдущий набор входных данных. Ваша программа должна немедленно завершиться для получения вердикта Неправильный ответ. В противном случае вы можете получить любой вердикт, так как программа продолжит чтение из закрытого потока.
После вывода запроса не забудьте вывести перевод строки и сбросить буфер вывода. В противном случае вы получите вердикт Решение «зависло». Для сброса буфера используйте:
- fflush(stdout) или cout.flush() в C++;
- System.out.flush() в Java;
- flush(output) в Pascal;
- stdout.flush() в Python;
- смотрите документацию для других языков.
Взломы
Чтобы сделать взлом, используйте следующий формат.
Первая строка должна содержать одно целое число \(t\) (\(1 \leq t \leq 10^4\)).
Первая строка каждого набора входных данных должна содержать одно целое число \(n\) (\(2 \leq n \leq 2 \cdot 10^4\)).
Вторая строка должна содержать \(n\) целых чисел \(p_1,p_2,\ldots,p_n\). \(p\) должно быть перестановкой чисел \([0,1,2,\ldots,n-1]\).
Сумма значений \(n\) не должна превосходить \(2 \cdot 10^4\).
Примечание
В первом примере взаимодействие происходит следующим образом.
| Решение | Жюри | Комментарий |
| \(\texttt{2}\) | В тесте 2 набора входных данных. |
| \(\texttt{2}\) | В первом наборе загадана перестановка \([1,0]\) длины \(2\). |
| \(\texttt{? 1 2}\) | \(\texttt{1}\) | Решение запрашивает \(\gcd(p_1,p_2)\), жюри отвечает \(1\). |
| \(\texttt{! 1 2}\) | \(\texttt{1}\) | Решение знает, что либо \(p_1=0\), либо \(p_2=0\), и выводит ответ. Так как ответ правильный, жюри отвечает \(1\) и переходит к следующему набору входных данных. |
| \(\texttt{5}\) | Во втором наборе загадана перестановка \([2,4,0,1,3]\) длины \(5\). |
| \(\texttt{? 1 2}\) | \(\texttt{2}\) | Решение запрашивает \(\gcd(p_1,p_2)\), жюри отвечает \(2\). |
| \(\texttt{? 2 3}\) | \(\texttt{4}\) | Решение запрашивает \(\gcd(p_2,p_3)\), жюри отвечает \(4\). |
| \(\texttt{! 3 3}\) | \(\texttt{1}\) | Решение каким-то образом определило, что \(p_3=0\), и выводит ответ. Так как ответ верный, жюри отвечает \(1\). |
Обратите внимание, что пустые строки в примерах ввода и вывода показаны для ясности и отсутствуют в настоящем взаимодействии.
Помните про считывание \(1\) или \(-1\) после каждого набора входных данных.