Задача №112876. Where is the one?

Еве на День святого Валентина подарили перестановку \(P\) из \(N\) чисел (то есть, массив из \(N\) различных чисел от \(1\) до \(N\)). Глеб хочет угадать, на какой позиции в этой перестановке находится число 1. Для этого он может задавать Еве вопросы одного из двух типов: 

  • g(i,j)
    Верно ли, что \(P_i > P_j\)?
  • f(i,j,d)
    Верно ли, что \(|P_i - P_j|\) делится на число \(d\)?
\(i\) и \(j\) должны являться корректными индексами от \(1\) до \(n\), а число \(d\) должно являться целым и положительным, не превосходящим \(10^9\).

Система оценки

Вам необходимо угадать позицию числа \(1\) в перестановке, используя минимально возможное количество вопросов первого типа. При этом, число вопросов второго типа не требуется минимизировать, однако оно должно быть разумным, иначе вы можете получить вердикт "Превышено время выполнения программы ". Во всех тестах выполнено \(1 \le n \le 500\,000\). При этом, в 28% тестов выполнено дополнительное ограничение \(n \le 5000\).

Формат взаимодействия с тестирующей системой

Эту задачу можно сдать лишь на языке C++! Без подключения чего-либо доступны следующие функции: 
  • inicjuj()
    Эта функция возвращает число \(n\). Данная функция должна быть вызвана в программе не более одного раза.
  • odpowiedz(k)
    Аргументом этой функции должен являться правильный ответ на задачу, то есть позиция числа \(1\) в перестановке. После вызова этой функции ваша программа немедленно завершиться!
  • f(i,j,k)
  • g(i,j)
Обратите внимание, что ваша программа не должна использовать функции ввода-вывода, за исключением, быть может, вывода в стандартный поток ошибок stderr. Здесь вы можете скачать пример решения.
Примеры
Входные данные
5
4
5
2
1
3
Выходные данные
1
Сдать: для сдачи задач необходимо войти в систему