Антону стало скучно в походе, и он захотел что-нибудь порешать. Он спросил у Кирилла, нет ли у него какой-то новой задачи, и у Кирилла она естественно нашлась.
Дана перестановка \(p\) размера \(n\), а также число \(x\), которое необходимо найти. Перестановкой длины \(n\) является массив, состоящий из \(n\) различных целых чисел от \(1\) до \(n\) в произвольном порядке. Например, \([2,3,1,5,4]\) — перестановка, но \([1,2,2]\) не перестановка (\(2\) встречается в массиве дважды) и \([1,3,4]\) тоже не перестановка (\(n=3\), но в массиве встречается \(4\)).
Вы решили, что вы крутой программист, поэтому будете использовать для поиска продвинутый алгоритм — бинарный поиск. Однако, вы забыли, что для бинарного поиска массив должен быть отсортирован.
Вы не отчаялись и решили все равно применить этот алгоритм, а чтобы получить правильный ответ, вы перед запуском алгоритма можете не более \(2\) раз выполнить следующую операцию: выбрать индексы \(i\), \(j\) (\(1\le i, j \le n\)) и поменять местами элементы на позициях \(i\) и \(j\).
После этого выполняется бинарный поиск. В начале алгоритма объявляются две переменные \(l = 1\) и \(r = n + 1\). Далее выполняется цикл:
- Если \(r - l = 1\), закончить цикл
- \(m = \lfloor \frac{r + l}{2} \rfloor\)
- Если \(p_m \le x\), присвоить \(l = m\), иначе \(r = m\).
Цель — до алгоритма переставить числа в перестановке так, чтобы после выполнения алгоритма \(p_l\) было равно \(x\). Можно показать, что \(2\) операции всегда достаточно.
Выходные данные
Для каждого набора входных данных выведите в первой строке целое число \(k\) (\(0 \le k \le 2\)) — количество совершенных вами операций. В следующих \(k\) строках через пробел выведите по \(2\) целых числа \(i\), \(j\) (\(1 \le i, j \le n\)) означающих, что вы меняете местами элементы на позициях \(i\) и \(j\).
Обратите внимание, что вам не нужно минимизировать количество операций.