Спитаємо спершу запит про всі елементи крім якогось одного. Зрозуміло, що нам повернуть , позицію числа \frac{n}{2} чи \frac{n}{2}+1. Тепер, якщо ми спитаємо запит про всі числа крім , ми отримаємо , позицію другого з цих чисел.
Помітимо, що наші запити не дозволяють відрізнити перестановку (p_1, p_2, \ldots, p_n) від перестановки (n+1-p_1, n+1-p_2, \ldots, n+1-p_n). Тому вважатимемо, що p_x = \frac{n}{2}, p_y = \frac{n}{2}+1, і знайдемо перестановку за цієї умови, а в кінці замінимо її на (n+1-p_1, n+1-p_2, \ldots, n+1-p_n), якщо виявиться що p_1>p_n.
Нехай на якомусь кроці ми знаємо позиції всіх чисел від до n+1-t. Тоді виберемо якесь , число в якому ми ще не знаємо, і спитаємо запит про всі позиції, числа в яких ми не знаємо, крім . Ми отримаємо x_1 — позицію числа t-1 чи n+2-t. Спитаємо тепер про всі позиції, числа в яких ми не знаємо, крім x_1, отримаємо y_1, позицію другого з цих чисел. Тепер нам треба зрозуміти, хто з p_{x_1} та p_{y_1} t-1, а хто n+2-t.
Для цього спитаємо запит з x_1, x, y. Якщо позицією медіани виявиться , то x_1 = t-1, інакше x_1 = n+2-t.
Таким чином, ми можемо знаходити позиції двох наступних чисел за операції.