Это интерактивная задача.
Мы загадали массив \(a_1, a_2, \ldots, a_n\) (\(0 \le a_i \le 10^9\)) и спрятали в нём один ноль! Более формально, среди чисел массива ровно одно значение равно нулю.
Ваша задача — найти, под каким индексом спрятан ноль, то есть найти такое \(i\), что \(a_i = 0\).
Для этого вы можете сделать некоторое количество запросов следующего вида. По трём различным индексам \(i, j, k\) вы можете узнать значение выражения \(\max(a_i, a_j, a_k) - \min(a_i, a_j, a_k)\). Другими словами, мы сообщим вам разность между максимальным и минимальным числом среди \(a_i\), \(a_j\) и \(a_k\).
Вы можете сделать не более \(2 \cdot n - 2\) таких запросов, после чего у вас будет две попытки угадать, под каким индексом спрятан ноль. Формально, вы должны сообщить нам два числа \(i\) и \(j\), и ваш ответ будет считаться правильным, если \(a_i = 0\) или \(a_j = 0\).
Сможете ли вы угадать, где мы спрятали ноль?
Обратите внимание, что в каждом тесте массив фиксирован и не изменяется во время игры. Иными словами, интерактор не адаптивен.
Протокол взаимодействия
Взаимодействие начинается со считывания \(n\) в начале каждого набора входных данных.
Чтобы задать запрос, выведите «? \(i\) \(j\) \(k\)» (без кавычек, \(1 \le i, j, k \le n\), индексы должны быть различны). Затем вы должны считать ответ, который будет равен \(\max(a_i, a_j, a_k) - \min(a_i, a_j, a_k)\).
Ответ \(-1\) означает, что ваша программа сделала некорректный запрос. Ваша программа должна немедленно завершиться после прочтения ответа \(-1\), и вы получите вердикт Неправильный ответ. В противном случае вы можете получить любой вердикт, так как программа продолжит чтение из закрытого потока. Обратите внимание, что если запрос корректный, ответ на него никогда не будет равен \(-1\), так как \(\max(a_i, a_j, a_k) - \min(a_i, a_j, a_k) \geq 0\).
Чтобы дать ответ, выведите «! \(i\) \(j\)» (без кавычек). Вывод одного и того же индекса дважды (то есть \(i = j\)) разрешен. Заметьте, что вывод ответа не считается одним из \(2 \cdot n - 2\) запросов. После этого ваша программа должна продолжить обработку следующих наборов входных данных, либо завершиться, если наборов не осталось.
После вывода каждого запроса не забудьте вывести перевод строки и сбросить буфер вывода. В противном случае вы получите вердикт Решение «зависло». Для сброса буфера используйте:
- fflush(stdout) или cout.flush() в C++;
- System.out.flush() в Java;
- flush(output) в Pascal;
- stdout.flush() в Python;
- смотрите документацию для других языков.
Взломы
Первая строка должна содержать целое число \(t\) (\(1 \le t \le 500\)) — количество наборов входных данных.
Первая строка каждого набора входных данных должна содержать целое число \(n\) (\(4 \le n \le 1000\)) — длину загаданного массива.
Вторая строка каждого набора должна содержать \(n\) целых чисел, разделенных пробелами — \(a_1, a_2, \ldots, a_n\) (\(0 \le a_i \le 10^9\)). Также в этом массиве должен быть ровно один ноль.
Сумма \(n\) по всем наборам не должна превосходить \(3000\).
Примечание
Массив из теста из примера: \([1, 2, 0, 3]\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
1
4
2
3
3
2
|
? 1 2 3
? 2 3 4
? 3 4 1
? 4 1 2
! 2 3
|